1
$\begingroup$

I came across this question. Palindromes are not regular: It is easy to prove it using pumping lemma. The problem is I want an explicit proof without pumping lemma. I came up with a solution. It goes like this. Let us assume a language L which is palindrome so L can be expressed as x.xR where xR is reverse of x. If x is a regular language then xR will be too and hence the palindrome will be regular. What if x is not a regular language. Lets say x is 1^n0^n. It is not possible to draw a DFA for this as this string needs memory to keep the count of 1s so that it can add exact number of 0s. Since DFA doesn't have memory so it wont be possible to make a DFA for this, but xR = 0^n1^n and L=x.xR that is 1^n0^n.0^n1^n is still palindrome but not a regular language. So we can say palindromes are not regular. I remember from my undergrad class to prove some language is not regular it is sufficient to give one negative example. Will this approach work?

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of How to prove that a language is not regular? $\endgroup$ – fade2black Sep 20 '17 at 5:56
  • 1
    $\begingroup$ Not clear what you mean by a "negative example". DFAs do have memory, but finite amount. If you do not want to use pumping lemma you can prove this language is not regular using Myhill-Nerode theorem. $\endgroup$ – fade2black Sep 20 '17 at 5:56
  • $\begingroup$ @fade2black Not just finite but constant. Even a Turing machine has only used a finite amount of memory at any stage of its computation. $\endgroup$ – David Richerby Sep 20 '17 at 9:40
  • $\begingroup$ Do DFA have memory? I thought DFA doesnt have and thats why we cannot solve problems like 0^n1^n using DFA. We need PDA for that $\endgroup$ – Shannu Sep 20 '17 at 11:16
  • $\begingroup$ Constant amount of memory containing constant amount of information (symbols) can be expressed as states of FA. For example if you have $3$ cells which may contain at most $2$ symbols ($0$ and $1$) then you could represent memory configurations using $6$ states: $(c_1,0), (c_1,1),(c_2,0), (c_2,1),(c_3,0), (c_3,1)$. So, when you write, for example $0$ to the cell $c_2$, you simply move into the state $(c_2,0)$. $\endgroup$ – fade2black Sep 20 '17 at 12:30
1
$\begingroup$

You can use the Myhill–Nerode criterion.

Suppose that $A$ is a DFA accepting your language. Let $q_n$ be the state which the DFA reaches upon reading the word $0^n1$. As the DFA has finitely many states, we must have $q_n = q_m$ for some $n \neq m$. On the one hand, when at state $q_n$, upon reading $0^n$ the DFA must reach an accepting state, since $0^n 1 0^n$ is a palindrome. On the other hand, when at state $q_m$, upon reading $0^n$ the DFA must reach a non-accepting state, since $0^m 1 0^n$ is not a palindrome. We have reached a contradiction since $q_n = q_m$.

$\endgroup$
  • $\begingroup$ In other words, you apply the Myhill–Nerode criterion to the language $\text{PAL} \cap 0^*10^* = \{0^n10^n \mid n \geqslant 0\}$. $\endgroup$ – J.-E. Pin Sep 20 '17 at 9:12
  • $\begingroup$ Yes, that's another way to put it. $\endgroup$ – Yuval Filmus Sep 20 '17 at 9:13
  • $\begingroup$ I got little confused here. First you have mentioned "Let qn be the state which the DFA reaches upon reading the word 0^n1." Later in the explanation we assumed ". On the one hand, when at state qn, upon reading 0^n ". Please help me understand. Thanks! $\endgroup$ – Shannu Sep 20 '17 at 11:52
  • $\begingroup$ When the DFA reads the word $0^n 1$ it reaches some state which I denoted $q_n$. When it then continues and reads the word $0^n$ it reaches some other state, which is also the same the DFA reaches when it reads the word $0^n10^n$ starting from its initial state. $\endgroup$ – Yuval Filmus Sep 20 '17 at 12:02
  • $\begingroup$ Got it! Thanks for the explanation. :) $\endgroup$ – Shannu Sep 20 '17 at 12:18
1
$\begingroup$

You can also use Kolmogorov Complexity.

Very informally:

  • suppose that there is a DFA $A$ for palindromes $L_A = \{ w w^r \mid w \in \{0,1\}^+ \}$
  • pick a long enough uncompressible string $x$ ( $|x| \gg |A|$ )
  • run $A$ on input $x^r x$ and suppose that it is in state $q_i$ after scanning the first half part of the input (i.e. after reading $x^r$)
  • then you can build a Turing machine $M$ that on input

$$\langle A, i, |x| \rangle$$

generates all strings $\{0,1\}^{|x|}$ and for each one "continues" the simulation of $A$ starting from $q_i$ until it finds the (unique) string accepted by $A$ which is exactly $x$.

But $|M| = |A| + \log i + \log |x| + c < |x|$ for a long enough $x$, in other words there is a program $M$ that is smaller than $|x|$ that generates the uncompressible string $x$; which is a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.