Question

In Exercises 16–22 find the language recognized by the given deterministic finite-state automaton

Short answer

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

Step-by-step solution

According to the figure.

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

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

Since \({{\bf{s}}_{\bf{1}}}\) and \({{\bf{s}}_{\bf{3}}}\) is encircled twice, a string will be recognized by the deterministic finite state automaton if we end at state \({{\bf{s}}_{\bf{1}}}\) or state \({{\bf{s}}_{\bf{3}}}\).

Find the final result.

If the string starts with a 0, then we move from state \({{\bf{s}}_{\bf{o}}}\) to \({{\bf{s}}_{\bf{1}}}\), while we always remain at the state \({{\bf{s}}_{\bf{o}}}\) and if the remaining string contains only 0’s from state \({{\bf{s}}_{\bf{1}}}\) to \({{\bf{s}}_{\bf{2}}}\), if come across a zero, and thus, all strings consisting of only 0’s and at least one0 are in recognized language.

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

If the string starts with a 1, then we remain at the state \({{\bf{s}}_{\bf{o}}}\) and obtained the first 0. We then remain at state \({{\bf{s}}_{\bf{o}}}\) if the remaining string contains only 0’ and thus all strings containing of only 1’s and at least one 0are in the recognized language.

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

However, it is also possible to end up at state \({{\bf{s}}_{\bf{3}}}\) if we obtain 1 followed by a bit. Thus, the sets of the strings ending at state \({{\bf{s}}_{\bf{1}}}\)followed by a 1 and at least one other bit are also 0 recognized languages:

\(\begin{array}{c}{\bf{\{ 0\} \{ 0\} *\{ 1\} \{ 0,1\} \{ 0,1\} * = \{ 0\} \{ 0\} *\{ 10,11\} \{ 0,1\} *}} \in {\bf{L(M)}}\\{\bf{\{ 1\} \{ 1\} *\{ 0\} \{ 0\} *\{ 1\} \{ 0,1\} (0,1\} * = \{ 1\} \{ 1\} *\{ 0\} \{ 0\} *\{ 10,11\} \{ 0,1\} *}} \in {\bf{L(M)}}\end{array}\)

Therefore, the language generated by the machine is:

\(\begin{aligned}{\bf{L(M) = \{ 0\} \{ 0\} *}} \cup {\bf{\{ 1\} \{ 1\} *\{ 0\} \{ 0\} }}* \cup {\bf{\{ 0\} \{ 0\} *\{ 10,11\} \{ 0,1\} }}* \cup {\bf{\{ 1\} \{ 1\} *\{ 0\} \{ 0\} *\{ 10,11\} \{ 0,1\} *}}\\{\bf{ = \{ 1\} *\{ 0\} \{ 0\} *}} \cup {\bf{\{ 1\} *\{ 0\} \{ 0\} *\{ 10,11\} \{ 0,1\} *}}\end{aligned}\)