Question

Find a deterministic finite-state automaton that recognizeseach of these sets.

\(\begin{array}{l}{\bf{a)\{ 0\} }}\\{\bf{b)\{ 1,00\} }}\\{\bf{c)\{ }}{{\bf{1}}^{\bf{n}}}{\bf{|n = 2,3,4,}}...{\bf{\} }}\end{array}\)

Short answer

The result is

(a)

State	0	1
\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{2}}}\)

b)

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

c)

State	0	1
\({{\bf{s}}_{\bf{0}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{1}}}\)
\({{\bf{s}}_{\bf{1}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\bf{s}}_{\bf{2}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{2}}}\)
\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)	\({{\bf{s}}_{\bf{3}}}\)

Step-by-step solution

Construction of deterministic finite-state automaton.

(a)

Here \(L\left( M \right) = \left\{ 0 \right\}\)

Let’s consider threestate\({s_0},{s_{1,}}{s_2}\).

Let start state be \({s_0}\).Since the empty string is not the final,\({s_0}\)is not a final state.

If the input start with a 0, then move on to a final state\({s_1}\). If the input contains any more digits, then move on to the non-final state\({s_2}\). Once arrive at\({s_2}\), will never leave the state again.

If the input starts with a 1, then move on to a non-final state\({s_2}\).

Other way of representing in tabular form.

State	0	1
\({s_0}\)	\({s_1}\)	\({s_2}\)
\({s_1}\)	\({s_2}\)	\({s_2}\)
\({s_2}\)	\({s_2}\)	\({s_2}\)

Construct deterministic finite-state automaton.

(b)

Here \(L\left( M \right) = \left\{ {1,00} \right\}\)

Let us consider fivestates\({s_0},{s_{1,}}{s_2},{s_3},{s_4}\).

Let start state be \({s_0}\).Since the empty string is not the final,\({s_0}\)is not a final state.

If the input start with a 0, then move on to a non- final state\({s_1}\). If the next input is 0 then move on to the final state\({s_2}\).if another input follows the two zeros of it the input was 1, then move on to a non-final state\({s_3}\),that will never leave again.

If the input starts with a 1, then move on to a final state\({s_4}\).If the input contains any more digits, then I move on to non-final state\({s_3}\). Once I arrive at\({s_2}\), I will never leave the state again.

Other way of representing in tabular form.

State	0	1
\({s_0}\)	\({s_1}\)	\({s_4}\)
\({s_1}\)	\({s_2}\)	\({s_3}\)
\({s_2}\)	\({s_3}\)	\({s_3}\)
\({s_3}\)	\({s_3}\)	\({s_3}\)
\({s_4}\)	\({s_3}\)	\({s_3}\)

Construction of deterministic finite-state automaton.

(c)

Here \(L\left( M \right) = \left\{ {{1^n}|n = 2,3,4,...} \right\}\)

Let us consider four states \({s_0},{s_{1,}}{s_2},{s_3}\).

Let start state be \({s_0}\).Since the empty string is not the final,\({s_0}\)is not a final state.

If the input start with a 1, then I move on to a non-final state\({s_1}\).

If the next input start with a 1, then I move on to a final state\({s_2}\)and any additional input of 1 should keep at the final state \({s_2}\).

If the input with a 0, then I move on to a non-final state\({s_3}\).Once I arrive at \({s_3}\), I will never leave the state again.

Other way of representing in tabular form.

State	0	1
\({s_0}\)	\({s_3}\)	\({s_1}\)
\({s_1}\)	\({s_3}\)	\({s_2}\)
\({s_2}\)	\({s_3}\)	\({s_2}\)
\({s_3}\)	\({s_3}\)	\({s_3}\)

Therefore, this is the require construction of all parts.