We know that general palindromes cannot be decided by a DFA.

Howeve if you restrict to case of even length palindromes, does a DFA need exactly $2^{2k}$ states where $2k$ is length of palindrome the language needs to accept?

I get this as lower bound from Myhill Nerode aplication.

From answers below, my lower bound is wrong. What is the correct bound from Myhill Nerode?

How do you show the upper bound?

  • $\begingroup$ What's your alphabet? $\endgroup$ – adrianN Oct 30 '15 at 7:50
  • $\begingroup$ $0,1$ is alphabet $\endgroup$ – T.... Oct 30 '15 at 7:56
  • $\begingroup$ You show the upper bound by constructing the DFA. $\endgroup$ – Yuval Filmus Oct 30 '15 at 8:01
  • $\begingroup$ Show us how you got $2^{2k}$ from M-N. $\endgroup$ – Rick Decker Oct 30 '15 at 17:21
  • $\begingroup$ @RickDecker here cs.stackexchange.com/questions/48906/… I think I am making mistake in not merging some length k+i strings. $\endgroup$ – T.... Oct 30 '15 at 17:50

Imagine we build the DFA from top to bottom to recognize palindromes of length $2k$. As usual, we'll use the states to "remember" the input seen so far. The DFA will consist of three parts:

  1. The states needed to represent the $2^k$ possible choices for the first $k$ characters. This will be a complete binary tree of depth $k$ with $2^k$ leaves and so will need $2^{k+1}-1$ nodes in total.
  2. The states needed to process the remaining $k$ inputs. This will consist of $k-1$ layers, each of which contains $2^k$ nodes for a total of $(k-1)2^k$ nodes. For example, suppose we had $k=3$ and after part (1) we were in state $q_{011}$, i.e., having seen input $\mathtt{011}$. Then on input $\mathtt{0}$ we would transition to the fail state, since $\mathtt{0110}$ could not be part of a 6-character palindrome. If, on the other hand, we saw $\mathtt{1}$ we would change to a state on the next level, since the current input $\mathtt{0111}$ could be part of a palindrome.
  3. Finally, we add an accept state and a reject state, with the appropriate transitions from the accept state to the reject state on either 0 or 1 and similarly from the reject state to itself on a 0 or a 1.

We will have $2^{k+1}-1$ states in stage (1), $(k-1)2^k$ states in stage (2) and the two states in stage (3) for a total of $(2^{k+1}-1)+(k-1)2^k+2=(k+1)2^k+1$ states.

It's not hard to use a Myhill-Nerode argument to show that the states are pairwise distinguishable and so this DFA is minimal.

  • $\begingroup$ what is the correct lower bound from Myhill Nerode? Could you please show that too? $\endgroup$ – T.... Oct 30 '15 at 15:57
  • $\begingroup$ What is $K$ here? Is it $2^{2k}$? $\endgroup$ – T.... Oct 30 '15 at 16:36
  • $\begingroup$ My mistake. $K$ should have been $k$, for palindromes of length $2k$. $\endgroup$ – Rick Decker Oct 30 '15 at 17:17

If your alphabet is 0,1, and you want to recognize a palindrome of size exactly $k$ you need $2^k$ states to store which string makes up the first half of your palindrome.

{} - {0} - {00}
  \    \ {01}
   \ {1} - {10}
       \ {11}

Then you need to mirror that tree there to consume the last read input. The edges are labeled with the last character in the left state. Missing edges lead to fail. The right empty state is accepting.

...{00} - {0} \
...{01} /       {} - fail
...{10} - {1} /
...{11} /

So I get $2*2^k$ plus a failure state. If you want to recognize all palindromes up to size $k$, you can nondeterministically guess $k$. You can work out if making that NFA deterministic produces the bound you stated in your question.

  • $\begingroup$ Your counting is a bit off. Compare your numbers to your figures. $\endgroup$ – Yuval Filmus Oct 30 '15 at 9:03
  • $\begingroup$ @YuvalFilmus what is the correct bound from Myhill Nerode? $\endgroup$ – T.... Oct 30 '15 at 15:56
  • $\begingroup$ The correct bound is the size of the minimum DFA. $\endgroup$ – Yuval Filmus Oct 30 '15 at 18:01

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.