Find a DFA for a finite set of palindromes

Question

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?

Answer 1

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.

Answer 2

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