Palindrome of fixed length 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?
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:


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.
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.
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.