Question

In Exercises 43–49 find the language recognized by the given nondeterministic finite-state automaton.

Short answer

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

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 down in 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{1}}}\),\({{\bf{s}}_{\bf{2}}}\)
\({{\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.

Find the final result.

The start state \({{\bf{s}}_{\bf{o}}}\) is also the final state, which implies that the empty strings \({\bf{\lambda }}\) is present in the recognized language.

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

To Move from \({{\bf{s}}_{\bf{o}}}\) the final state \({{\bf{s}}_{\bf{1}}}\) (directly), I require that the input is 0 or 1 and thus the bit string 0 and 1 are both in recognized language.

\(0,1 \in {\bf{L(M)}}\)

To move from \({{\bf{s}}_{\bf{o}}}\) to \({{\bf{s}}_{\bf{2}}}\), the input has to be a 1. Then move from \({{\bf{s}}_{\bf{1}}}\)to \({{\bf{s}}_{\bf{2}}}\), the input needs to be 0. However, since there is a loop at \({{\bf{s}}_{\bf{2}}}\) for input 1. The string needs to have at least one 1 before the 0 to go from \({{\bf{s}}_{\bf{o}}}\) to \({{\bf{s}}_{\bf{1}}}\) and \({{\bf{s}}_{\bf{1}}}\) to \({{\bf{s}}_{\bf{2}}}\).

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

Therefore, the language generated by the machine is

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