Question

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

Short answer

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

Step-by-step solution

According to the figure

Here the given figure contains six states\({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{4}}},{{\bf{s}}_{\bf{5}}}\).

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{2}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{1}}}\),\({{\bf{s}}_{\bf{3}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\),\({{\bf{s}}_{\bf{3}}}\),\({{\bf{s}}_{\bf{4}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_{\bf{5}}}\)
\({{\bf{s}}_{\bf{4}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{5}}}\)
\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_{\bf{5}}}\)

\({{\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 string \({\bf{\lambda }}\)is present in the recognized language.

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

To Move from \({{\bf{s}}_{\bf{o}}}\) the final state\({{\bf{s}}_{\bf{1}}}\), I require that the input is 0 or 1. Thus the string 0 and 1 will be in recognized language. Moreover, there is also a loop at \({{\bf{s}}_{\bf{1}}}\)with input 1, which means that the number can end with any sequence of 1’s as well.

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

To Move from \({{\bf{s}}_{\bf{o}}}\) the final state\({{\bf{s}}_{\bf{2}}}\), I require that the input is 0. Moreover, there is also a loop at \({{\bf{s}}_{\bf{1}}}\)with input 0, which means that the number can end with any sequence of 0’s and 1’s as well.

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

To move from\({{\bf{s}}_{\bf{2}}}\)to the final state\({{\bf{s}}_{\bf{4}}}\), I require that the input is 0. Thus, any string in followed by a 0 is also in the subset.

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

Therefore, the language generated by the machine is

\(\begin{array}{l}{\bf{L(M) = \{ \lambda \} }} \cup {\bf{\{ 0,1\} \{ 1\} *}} \cup {\bf{\{ 0\} \{ 0,1\} *}} \cup {\bf{\{ 0\} \{ 0,1\} *\{ 0\} }}\\{\bf{L(M) = \{ 1\} *}} \cup {\bf{\{ 0)\{ }}0,{\bf{1\} *}}\end{array}\)