The Gateway to Computer Science Excellence
0 votes

Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement.

  1. $\{0^{n}1^{m}0^{n}|m,n\geq 0\}$
  2. $\{0^{m}1^{n}|m\neq n\}$
  3. $\{w|w\in\{0,1\}^{*}  \text{is not a palindrome}\}$
  4. $\{wtw|w,t\in\{0,1\}^{+}\}$
in Theory of Computation by | 54 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,497 answers
95,315 users