Question

Find a nondeterministic finite-state automaton that recognizes each of the languages in Exercise 55, and has fewer states, if possible, than the deterministic automaton you found in that exercise.

Short answer

The result is

(a)

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

b)

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

c)

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

Step-by-step solution

Construction of deterministic finite-state automaton.

(a)

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

Let us consider twostate\({s_0},{s_1}\).

In the deterministic finite state of the exercise(55),I made sure that all strings not should not be recognized ended up in the non-final state\({s_2}\).

The non-final state \({s_2}\)is then not useful for all strings that are actually recognised by the machine and thus I can remove \({s_2}\)from the deterministic finite automation to determine a non-deterministic finite-state automation.

Other way of representing in tabular form.

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

Construct deterministic finite-state automaton.

(b)

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

Let us consider five state\({s_0},{s_{1,}}{s_2},{s_3}\).

In the deterministic finite state of the exercise (55),I made sure that all strings not should not be recognized ended up in the non-final state\({s_3}\).

The non-final state \({s_3}\)is then not useful for all strings that are actually recognised by the machine and thus I can remove \({s_3}\)from the deterministic finite automation to determine a non-deterministic finite-state automation.

Other way of representing in tabular form.

State	0	1
\({s_0}\)	\({s_1}\)	\({s_3}\)
\({s_1}\)	\({s_2}\)
\({s_2}\)
\({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 state\({s_0},{s_{1,}}{s_2}\).

In the deterministic finite state of the exercise (55),I made sure that all strings not should not be recognized ended up in the non-final state\({s_2}\).

The non-final state\({s_2}\)is then not useful for all strings that are actually recognised by the machine and thus I can remove \({s_2}\)from the deterministic finite automation to determine a non-deterministic finite-state automation.

Other way of representing in tabular form.

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

Therefore, this is the require construction of all parts.