Question

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

Short answer

The result is \({\bf{L(M) = \{ 0\} *\{ 1\} \{ 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{o}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)

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

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

Find the final result.

If the string starts with a 1, then we move from state \({{\bf{s}}_{\bf{o}}}\) to \({{\bf{s}}_{\bf{1}}}\), while we always remain at the state \({{\bf{s}}_{\bf{1}}}\) and if the remaining string contains only 1’s from state \({{\bf{s}}_{\bf{1}}}\) to \({{\bf{s}}_{\bf{2}}}\) if come across zero and always remain at state \({{\bf{s}}_{\bf{2}}}\), and thus all strings consisting of only 1’s and at least one 1 are in recognized language.

\({\bf{\{ }}1{\bf{\} \{ 1\} *}} \ in {\bf{L(M)}}\)

If the string starts with a 0, then we remain at the state \({{\bf{s}}_{\bf{o}}}\) and obtained the first 1. We then remain at state \({{\bf{s}}_{\bf{1}}}\) if the remaining string contains only 1’ and thus all strings containing of only 1’s and at least one 1 a 1 are in the recognized language.

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

Hence, the language generated by the machine is:

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