Question

Using the constructions described in the proof of Kleene’s theorem, find non-deterministic finite-state automata that recognize each of these sets.

1. \({\bf{0*1*}}\)
2. \(\left( {0 \cup 11} \right){\bf{*}}\)
3. \(0{\bf{1*}} \cup {\bf{00*}}1\)

Short answer

1. Therefore, the nondeterministic finite-state automata that recognize the set \({\bf{0*1*}}\) are shown below.

2. Hence, the nondeterministic finite-state automata that recognize the set \(\left( {0 \cup 11} \right){\bf{*}}\)are shown below.

3. So, the nondeterministic finite-state automata that recognize the set \(0{\bf{1*}} \cup {\bf{00*}}1\)are shown below.

Step-by-step solution

General form

Finite-state automaton (Definition): A finite-state automaton \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) consists of a finite set S of states, a finite input alphabet I, a transition function f that assigns the next state to every pair of states and input (so that \({\bf{f:S \times I}} \to {\bf{S}}\)), an initial or start state \({{\bf{s}}_0}\), and a subset F of S consisting of final (or accepting states).

Kleene’s theorem: A set is regular if and only if it is recognized by a finite-state automaton.

Rules of regular expression represent a set:

\(\emptyset \)represents the empty set, that is, the set with no strings;

\({\bf{\lambda }}\)represents the set\(\left\{ {\bf{\lambda }} \right\}\), which is the set containing the empty string;

x represents the set \(\left\{ {\bf{x}} \right\}\) containing the string with one symbol x;

(AB) represents the concatenation of the sets represented by A and by B;

\(\left( {{\bf{A}} \cup {\bf{B}}} \right)\)represents the union of the sets represented by A and by B;

\({\bf{A*}}\)represents the Kleene closure of the sets represented by A.

Step 2: Construct the nondeterministic finite-state automata

Given,\({\bf{0*1*}}\)

In the second outline of Kleene's theorem's proof, the nondeterministic finite-state automata that recognize \({\bf{0*}}\) is shown, and the non-deterministic finite-state automata that recognize \(1{\bf{*}}\) is the same machine with the 0s changed to 1s.

The next step is to combine these two machines, which is accomplished by using the same input as the first machine and by drawing an arrow from the first machine's start state to the second machine's start state.

So, the diagram of the non-deterministic finite-state automaton is shown below.

Construct the nondeterministic finite-state automata

Given,\(\left( {0 \cup 11} \right){\bf{*}}\)

The third image in Kleene's theorem proof provides the nondeterministic finite-state automata that can recognize 0; the fourth image provides the nondeterministic finite-state automata that can recognize 11. Concatenating the two machines to the same start state allows us to take their union.

Following that, we must take Kleene's closure of this machine, which is accomplished by turning the initial state into a final state, adding loops and cycles to each machine in the union, and switching machines whenever the input changes to another term in the union.

So, the diagram of the non-deterministic finite-state automaton is shown below.

Construct the nondeterministic finite-state automata

Given,\(0{\bf{1*}} \cup {\bf{00*}}1\)

The nondeterministic finite-state automata that recognize 0 are given in the third image of the proof of Kleene’s theorem, whereas the nondeterministic finite-state automata that recognizes \(1{\bf{*}}\) is presented in the second image of the proof of Kleene's theorem. We need to concate these two machines to achieve\(01{\bf{*}}\).

The nondeterministic finite-state automata that can recognize 0 are shown in the third image of Kleene's theorem's proof, while the nondeterministic finite-state automata that can recognize \(0{\bf{*}}\) is shown in the second image.

The nondeterministic finite-state automata that can recognize 1 are similar to the machine that can recognize 0. To get this\(00{\bf{*}}1\), we must combine these three devices.

By connecting the two submachines to the same start state, we may finally take the union of these two acquired machines.

So, the diagram of the deterministic finite-state automaton is shown below.