# Find a DFA for a finite set of palindromes

Since every finite language is regular, I'm trying to find how would a DFA for the following language $\{xx^R \mid x \in \{a,b\}^*, |x| = \ell\}$ look like. Would there be one DFA for all words of length $\ell$ or one DFA per word?

• Well, the presented langauge is finite so long as $l$ is fixed. – jmite Jun 2 '16 at 0:32
• Closely related: cs.stackexchange.com/questions/53279/… – reinierpost Jun 2 '16 at 7:44
• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Jun 2 '16 at 9:34

To add to Denis' answer, depending on your tastes, one could also (trivially) construct a collection of FAs $M_i$ such that $M_i$ accepts only $w_i$ and from those construct a NFA by adding a new start state and linking that state to the original start states of each $M_i$ by $\epsilon$-moves. Having done that, constructing an equivalent DFA $D$ is straightforward, by a well-known process. In other words, we construct one DFA for each word and use them to construct one DFA for all words.
Consider a finite language $L$ over alphabet $\Sigma$, i.e., $|L| = k < \infty$. Let's enumerate all words of $L$ as follows $w_1, w_2, \ldots, w_k$. Let $S$ be the set of all prefixes of words of $L$. Create a DFA as follows: introduce a state $q(x)$ for each $x \in S$. For each compatible $x$ and $a$, define a transition rule $q(x) \rightarrow^a q(x a)$ where compatible means $x \in S$, $a \in \Sigma$, and $x a \in S$. Make states $q(w_i)$ accepting for each $i \in \{1, \ldots, k\}$. Any undefined transition leads to rejection. This DFA clearly accepts the $w_i$ and nothing else.
You can apply this construction to your particular case $L = \{ x x^R \mid x \in \{a,b\}^*, |a| = \ell\}$ with $|L| = 2^\ell$, i.e., there will be one DFA accepting all relevant words of length $\ell$. For example, consider $\ell = 1$. This means your $L = \{aa, bb\}$. The set of prefixes $S = \{\epsilon, a, b, aa, bb\}$. Your accepting states are $q(aa)$ and $q(bb)$ and your transition rules are $q(\epsilon) \rightarrow^a q(a)$, $q(a) \rightarrow^a q(aa)$, $q(\epsilon) \rightarrow^b q(b)$, $q(b) \rightarrow^b q(bb)$.