490 views
0 votes
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\}^{+}\}$

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
admin asked Apr 30, 2019
663 views
Let $A$ be any language. Define $\text{DROP-OUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\t...