Question

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

Short answer

The result is\({\bf{L(M) = \{ 100,101\} *}} \cup {\bf{\{ 1\} \{ 001,011\} *}}\).

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

\({{\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 1. Thus, the string 1 will be in recognized language.

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

To move from\({{\bf{s}}_{\bf{o}}}\)to\({{\bf{s}}_{\bf{2}}}\), the input has to be a 0. The input needs to start with 10. To then move from \({{\bf{s}}_{\bf{2}}}\)to \({{\bf{s}}_{\bf{o}}}\), the input can be anything and thus the strings need to start with 1000 or 101. Since I can execute the circuit from \({{\bf{s}}_{\bf{o}}}\)to\({{\bf{s}}_{\bf{o}}}\) as many times as possible.

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

To move from\({{\bf{s}}_{\bf{1}}}\)to\({{\bf{s}}_{\bf{2}}}\), the input has to be a 10. To then move from \({{\bf{s}}_{\bf{2}}}\)to \({{\bf{s}}_{\bf{o}}}\), the input can be anything and thus the strings need to start with 1000 or 101. To move from\({{\bf{s}}_{\bf{o}}}\)to \({{\bf{s}}_{\bf{1}}}\)again, I require that the input 1 and thus the strings need to start with 1001 or 1011. Since I can execute the circuit from \({{\bf{s}}_{\bf{1}}}\)to \({{\bf{s}}_{\bf{1}}}\)as many times as possible, the recognized language contains all strings starting with a 1,followed with as many repetitions of 001 or 011 as possible.

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

Therefore, the language generated by the machine is

\(\begin{array}{l}{\bf{L(M) = \{ \lambda }},1{\bf{\} }} \cup {\bf{\{ }}10{\bf{0\} \{ 1}}01{\bf{\} *}} \cup {\bf{\{ 1\} \{ 001,011\} }}\\{\bf{L(M) = \{ 100,101\} *}} \cup {\bf{\{ 1\} \{ 001,011\} *}}\end{array}\)