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\} \{ 0\} *}} \cup {\bf{\{ 1\} \{ 0\} *\{ 1\} \{ 0\} *}}\).

Step-by-step solution

According to the figure.

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

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

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

Find the final result.

To Move from \({{\bf{s}}_{\bf{o}}}\) the final state \({{\bf{s}}_{\bf{1}}}\) (directly), I require that the input is 1. Thus,the string 1 will be in recognized language.

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

Since there is also a loop at \({{\bf{s}}_{\bf{1}}}\)with input 0,the strings can also end with any number of 0’s.

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

To move from \({{\bf{s}}_{\bf{1}}}\)to final state\({{\bf{s}}_{\bf{3}}}\), the input has to be a 1.However, there is also a loop as \({{\bf{s}}_{\bf{1}}}\) for the input 0,which implies that it arrives at \({{\bf{s}}_{\bf{3}}}\)is the string starts with a 1,followed by a sequence of 0’s and ending with a 1.Since there is also a loop at \({{\bf{s}}_{\bf{3}}}\)with input 0,the strings can also end with any number of 0’s.

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

If lmoves from \({{\bf{s}}_{\bf{o}}}\) to \({{\bf{s}}_{\bf{2}}}\), then it is not possible to get to one of the final states\({{\bf{s}}_{\bf{1}}}\)or \({{\bf{s}}_{\bf{3}}}\).

Therefore, the language generated by the machine is

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