-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Well, the presented langauge is finite so long as $l$ is fixed. $\endgroup$ – jmite Jun 2 '16 at 0:32
  • 1
    $\begingroup$ Closely related: cs.stackexchange.com/questions/53279/… $\endgroup$ – reinierpost Jun 2 '16 at 7:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jun 2 '16 at 9:34
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That is, Thompson's construction. (or something very similar). $\endgroup$ – Raphael Jun 2 '16 at 9:35
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.