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\} \{ 1\} \{ 0\} }} \cup {\bf{\{ 10,11\} \{ 0,1\} }} \cup {\bf{\{ 0\} \{ 1\} \{ 01\} \{ 0,1\} }} \cup {\bf{\{ 0\} \{ 1\} \{ 00\} \{ 0\} \{ 1\} \{ 0,1\} }}*\)

Step-by-step solution

According to the figure.

Here the given figure contains five states\({{\bf{s}}_{\bf{o}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}{\bf{,}}{{\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 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{3}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_4}\)	\({{\bf{s}}_4}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_4}\)
\({{\bf{s}}_{\bf{4}}}\)	\({{\bf{s}}_4}\)	\({{\bf{s}}_4}\)
\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_{\bf{5}}}\)	\({{\bf{s}}_4}\)

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

Find the final result.

Because\({{\bf{s}}_{\bf{o}}}\)is the final state, the empty string is accepted. The string that drives the machine to the final state \({{\bf{s}}_{\bf{3}}}\)is precise\({\bf{\{ 0\} \{ 1\} \{ 0\} }}\).

There are three ways to get to the final state\({{\bf{s}}_{\bf{4}}}\), and once I get three, I stay there. The path thorough \({{\bf{s}}_{\bf{2}}}\)tells those strings in \({\bf{\{ 10,11\} \{ 0,1\} }}\) are accepted.

The path \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{4}}}\) tells that the strings in \({\bf{\{ 0\} \{ 1\} \{ 01\} \{ 0,1\} }}\) are accepted and the path \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{\bf{,}}{{\bf{s}}_{\bf{5}}},{{\bf{s}}_{\bf{4}}}\)tells those strings in \({\bf{\{ 0\} \{ 1\} \{ 00\} \{ 0\} \{ 1\} \{ 0,1\} *}}\)are accepted.

Therefore, the language recognized by machines is:

\({\bf{L(M) = }}\lambda \cup {\bf{\{ 0\} \{ 1\} \{ 0\} }} \cup {\bf{\{ 10,11\} \{ 0,1\} }} \cup {\bf{\{ 0\} \{ 1\} \{ 01\} \{ 0,1\} }} \cup {\bf{\{ 0\} \{ 1\} \{ 00\} \{ 0\} \{ 1\} \{ 0,1\} }}*\)