Question

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

Short answer

The result is \({\bf{L(M) = \{ \lambda \} }} \ cup {\bf{\{ }}0{\bf{\} \{ 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{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\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{o}}}\) and \({{\bf{s}}_{\bf{1}}}\) is encircled twice, a string will be recognized by the deterministic finite state automaton if we end at state \({{\bf{s}}_{\bf{o}}}\) or state \({{\bf{s}}_{\bf{1}}}\).

We can only end at state \({{\bf{s}}_0}\) if the input is the empty string since there are no arrows from a state to \({{\bf{s}}_0}\).

Find the final result.

Let \({\bf{\lambda }} \ in {\bf{L(M)}}\)

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

If the string starts with a 0, then we move from state \({{\bf{s}}_{\bf{o}}}\) to \({{\bf{s}}_{\bf{1}}}\). We then only remain at state \({{\bf{s}}_{\bf{1}}}\) if the string next contains only 1’s on to state \({{\bf{s}}_{\bf{2}}}\), when we have a second 0 and then remains at the state \({{\bf{s}}_{\bf{2}}}\) and thus any string starting with a 0 followed by any number of 1’s will in the recognized language.

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

Hence, the language generated by the machine is:

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