# 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. Commented Jun 2, 2016 at 0:32
• Closely related: cs.stackexchange.com/questions/53279/… Commented Jun 2, 2016 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. Commented Jun 2, 2016 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)$.