Question

In Exercises 16–22 find the language recognized by the given deterministic finite-state automaton

Short answer

The result is \({\bf{L(M) = \{ }}1{\bf{\} \{ }}0,{\bf{1\} }}* \cup {\bf{\{ 10,11\} \{ 0,1\} * = \{ 0,10,11\} \{ 0,1\} *}}\)

Step-by-step solution

According to the figure.

Here the given figure contains three states \({{\bf{s}}_{\bf{o}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}\).

If there is an arrow from \({{\bf{s}}_{\bf{i}}}\) to \({{\bf{s}}_{\bf{j}}}\) with label x, then we write it down in a row \({{\bf{s}}_{\bf{j}}}\) and in the row \({{\bf{s}}_{\bf{i}}}\) and in column x of the following table.

State	0	1
\({{\bf{s}}_{\bf{o}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)

\({{\bf{s}}_{\bf{o}}}\)is marked as the start state.

Since \({{\bf{s}}_{\bf{2}}}\) is encircled twice, a string will be recognized by the deterministic finite state automaton if we end at state \({{\bf{s}}_{\bf{2}}}\).

Find the final result.

If the string starts with a 0, then we move from state \({{\bf{s}}_{\bf{o}}}\) to \({{\bf{s}}_{\bf{1}}}\), while we always remain at the state and thus any string \({{\bf{s}}_{\bf{2}}}\) and thus any string starting with a 0 is included in the recognized language.

\({\bf{\{ }}0{\bf{\} \{ 0,1\} *}} \subseteq {\bf{L(M)}}\)

If the string starts with a 1, then we move from state \({{\bf{s}}_{\bf{o}}}\)to \({{\bf{s}}_{\bf{2}}}\). we then only move on from state \({{\bf{s}}_{\bf{1}}}\) to \({{\bf{s}}_{\bf{2}}}\) if we string obtains a second bit, while we always remain at the state \({{\bf{s}}_{\bf{2}}}\) , and thus any string starting containing a 1 followed by a bit is included in the recognized language.

\({\bf{\{ }}1{\bf{\} \{ }}0,{\bf{1\} }}\{ 0,1\} * = {\bf{\{ }}1{\bf{0}},11{\bf{\} \{ 0,1\} }}* \ subseteq {\bf{L(M)}}\)

The language generated by the machine is:

\({\bf{L(M) = \{ }}1{\bf{\} \{ }}0,{\bf{1\} }}* \cup {\bf{\{ 10,11\} \{ 0,1\} * = \{ 0,10,11\} \{ 0,1\} *}}\)