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.


1 Answer 1


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

  • $\begingroup$ Thank you! For proving this, would i induct on length of w ? $\endgroup$
    – Mandy
    Commented Sep 29, 2019 at 22:58
  • $\begingroup$ Right, induction is on the length of the word. $\endgroup$ Commented Sep 29, 2019 at 23:04
  • $\begingroup$ Thanks this is super helpful :) $\endgroup$
    – Mandy
    Commented Sep 29, 2019 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
    Commented Sep 29, 2019 at 23:54
  • $\begingroup$ No, $S$ ought to contain all prefixes. $\endgroup$ Commented Sep 30, 2019 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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