Palindrome of fixed length

Question

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?

Answer 1

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.

Answer 2

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.