# Method to construct a finite state machine for a finite-size language L

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.

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$$.
• 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. – Mandy Sep 29 at 23:54
• No, $S$ ought to contain all prefixes. – Yuval Filmus Sep 30 at 7:02