2
$\begingroup$

I need to define a method to construct a finite automata for a finite language L (part of my proof for something else). My idea:

  1. Create $|L|$ accepting states.
  2. For each input string $s$ from $L$, create appropriate transitions from a starting state to unique accepting state of s.

I don't know how to formally describe this, or if this idea is even good.

$\endgroup$
1
$\begingroup$

Let $S$ be the list of all prefixes of words in $L$. Create a DFA with a state $q_s$ for each $s \in S$, and an additional sink state $q_\bot$. The starting state is $q_\epsilon$, and a state is accepting if it corresponds to a word in $L$. When at a non-sink state $q_s$, upon reading $\sigma$, move to $q_{s\sigma}$ if $s\sigma \in S$, and to $q_\bot$ otherwise. When at $q_\bot$, always stay there.

To show that this works, prove inductively that when reading a word $w$, if $w \in S$ then the DFA is at state $q_w$, and otherwise it's at state $q_\bot$.

$\endgroup$
  • $\begingroup$ Thank you! For proving this, would i induct on length of w ? $\endgroup$ – Mandy Sep 29 at 22:58
  • $\begingroup$ Right, induction is on the length of the word. $\endgroup$ – Yuval Filmus Sep 29 at 23:04
  • $\begingroup$ Thanks this is super helpful :) $\endgroup$ – Mandy Sep 29 at 23:06
  • $\begingroup$ One thing I'd add, S is a set of all $proper$ prefixes of words in L since prefix that's the word itself should be omitted in this case. $\endgroup$ – Mandy Sep 29 at 23:54
  • $\begingroup$ No, $S$ ought to contain all prefixes. $\endgroup$ – Yuval Filmus Sep 30 at 7:02

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.