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

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

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

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

We can only end at state \({{\bf{s}}_{\bf{o}}}\), if the input is the empty string, since there is no arrow from a state to \({{\bf{s}}_{\bf{o}}}\).

Find the final result.

Let \({\bf{\lambda }} \in {\bf{L(M)}}\)

If the string starts with a 1, then we move from state \({{\bf{s}}_{\bf{o}}}\) to \({{\bf{s}}_{\bf{1}}}\), while we always remain at state and thus any string \({{\bf{s}}_{\bf{1}}}\) starting with a 1 is included in the recognized language.

If the string start with a 0, then we move from state \({{\bf{s}}_{\bf{o}}}\)to \({{\bf{s}}_{\bf{2}}}\).we then only move on from state \({{\bf{s}}_{\bf{2}}}\)to \({{\bf{s}}_{\bf{1}}}\) if we string obtains a second zero, while we always remains at state \({{\bf{s}}_{\bf{1}}}\) and thus any string starting containing at least two 0’s is included in the recognised language.

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

Therefore, the language generated by the machine is:

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