I have a question about constructing an automaton for given language: $$L = \{000, 010, 100, 110\}$$ Solution for this was given below. Can anyone explain why this automaton accepts the language? This is not from my class. I got this from the web to study. What is the trap state do?
Note that $L$ is the set of all $3$-bit strings that end in $0$, irrespective of the first two bits. Suppose that we feed a $3$-bit string into this automaton. The initial state is $q_0$, so we start there, and the first input always causes a transition to state $q_1$. The second input always causes a transition to state $q_2$, so after reading two bits, the automaton will always be in state $q_2$, and an input of $0$ at this point sends it to the final (or acceptor) state $\text{Fin}$. Thus, every $3$-bit word ending in $0$ is accepted by the automaton, and these are precisely the words in $L$.
Before we can say that $L$ is the language accepted by the automaton, however, we must show that the automaton does not accept any word that is not in $L$. If the input is shorter than $3$ bits, the automaton ends up in state $q_0,q_1$, or $q_2$, and the word is not accepted. If the word has a third bit of $0$ but is more than $3$ bits long, the first three bits take the automaton to state $\text{Fin}$, the fourth bit then takes it to state $q_4$, and any further bits leave it in state $4$. Similarly, if the string is at least $3$ bits long, but the third bit is a $1$, that third bit takes the automaton to state $q_4$, and any further bits leave it there. Since $q_4$ is not a final (or acceptor) state, the automaton does not accept any of these words. Therefore it accepts precisely the words in $L$.
The trap state, is exactly that: once the automaton enters that state, it can never leave it, so it’s trapped there. The automaton is sent to the trap state whenever the input reaches a point such that no matter what further input there may be, the input word should not be accepted. Here that happens when the input string has a third bit of $1$ or is more than $3$ bits long: in both of those cases we know that the input string cannot possibly be in $L$.
The core of your automaton is $$ \to q_0 \xrightarrow{0,1} q_1 \xrightarrow{0,1} q_2 \xrightarrow{0} f \to $$ which is indeed an incomplete deterministic automaton recognizing your language. Now, if you want to make it complete, there are three transitions missing: $q_2 \xrightarrow{1} *$, $f \xrightarrow{0} *$ and $f \xrightarrow{1} *$. So you just create a new state $q_4$ and replace every occurrence of * by $q_4$: $q_2 \xrightarrow{1}\ q_4$, $f \xrightarrow{0} q_4$ and $f \xrightarrow{1} q_4$. Now you are still missing the transitions issued from $q_4$, but you apply the same algorithm to get $q_4 \xrightarrow{0}\ q_4$ and $q_4 \xrightarrow{1}\ q_4$. The state $q_4$ is a trap (or sink) state.
This is an instance of a generic algorithm to convert an incomplete DFA into a complete one: it suffices to add a new trap state.
you can accept words, but accepting languages is not mentioned (or at least I didn't see that).
– Patrick Da Silva Oct 28 '13 at 00:17eChungoo: How is the transition map $\delta$ defined for this automaton? Assuming $\delta(q_2,0) = \text{Fin}$ (and my above guess re. your meaning of "accepts the language"), then a run on any of the strings in $L$ ends at $\text{Fin}$, which I'm guessing is an accept state (is it?).
– Dan Oct 28 '13 at 00:29