Question

Construct a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar \({\bf{G = }}\left( {{\bf{V,T,S,P}}} \right)\), where \({\bf{V = }}\left\{ {{\bf{0,1,S,A,B}}} \right\}{\bf{,T = }}\left\{ {{\bf{0,1}}} \right\}{\bf{,S}}\) is the start symbol, and the set of productions is.

1. \({\bf{S}} \to 0{\bf{A,S}} \to 1{\bf{B,A}} \to 0{\bf{,B}} \to 0.\)
2. \({\bf{S}} \to 1{\bf{A,S}} \to 0{\bf{,S}} \to {\bf{\lambda ,A}} \to 0{\bf{B,B}} \to 1{\bf{B,B}} \to 1.\)
3. \({\bf{S}} \to 1{\bf{B,S}} \to 0{\bf{,A}} \to 1{\bf{A,A}} \to 0{\bf{B,A}} \to 1{\bf{,A}} \to 0{\bf{,B}} \to 1.\)

Short answer

1. Therefore, the nondeterministic finite-state automata that recognize the set \({\bf{S}} \to 0{\bf{A,S}} \to 1{\bf{B,A}} \to 0{\bf{,B}} \to 0\) is shown below.

2. Hence, the nondeterministic finite-state automata that recognize the set \({\bf{S}} \to 1{\bf{A,S}} \to 0{\bf{,S}} \to {\bf{\lambda ,A}} \to 0{\bf{B,B}} \to 1{\bf{B,B}} \to 1\)are shown below.

3. So, the nondeterministic finite-state automata that recognize the set \({\bf{S}} \to 1{\bf{B,S}} \to 0{\bf{,A}} \to 1{\bf{A,A}} \to 0{\bf{B,A}} \to 1{\bf{,A}} \to 0{\bf{,B}} \to 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 a next state to every pair of state 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).

Regular expressions (Definition):The regular expressions over a set I are defined recursively by:

The symbol \(\emptyset \) is a regular expression;

The symbol \({\bf{\lambda }}\) is a regular expression;

The symbol xis a regular expression whenever\({\bf{x}} \in {\bf{I}}\);

The symbols \(\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}\) and \({\bf{A*}}\) are regular expressions whenever A and B are regular expressions.

The sets represented by regular expressions are called regular sets.

Theorem 2:A set is generated by a regular grammar if and only if it is a regular set.

A rule of regular expression represents 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 that, recognizes the language generated by the regular grammar\({\bf{G = }}\left( {{\bf{V,T,S,P}}} \right)\), where \({\bf{V = }}\left\{ {{\bf{0,1,S,A,B}}} \right\}{\bf{,T = }}\left\{ {{\bf{0,1}}} \right\}{\bf{,S}}\) is the start symbol, and the set of productions is,

Given,\({\bf{S}} \to 0{\bf{A,S}} \to 1{\bf{B,A}} \to 0{\bf{,B}} \to 0.\)

Construction:

The initial state,\({{\bf{s}}_0}\), which corresponds to S, is initially drawn.

Then, using input 0, we draw an arrow from state\({{\bf{s}}_0}\), which stands for the production\({\bf{S}} \to 0{\bf{A}}\), to state\({{\bf{s}}_{\bf{A}}}\).

Then, using input 1, we draw an arrow from state \({{\bf{s}}_0}\) to state\({{\bf{s}}_{\bf{B}}}\), which stands in for production\({\bf{S}} \to 1{\bf{B}}\).

In order to depict the productions \({\bf{A}} \to 0\) and\({\bf{B}} \to 0\), we then draw arrows from \({{\bf{s}}_{\bf{A}}}\)and \({{\bf{s}}_{\bf{B}}}\) to F with input 0. The final state is assumed to be F.

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

So, the result shows that the required nondeterministic finite-state automata.

Construct the nondeterministic finite-state automata

Given,\({\bf{S}} \to 1{\bf{A,S}} \to 0{\bf{,S}} \to {\bf{\lambda ,A}} \to 0{\bf{B,B}} \to 1{\bf{B,B}} \to 1.\)

Construction:

As one of the production criteria is\({\bf{S}} \to {\bf{\lambda }}\), the beginning state\({{\bf{s}}_0}\), which corresponds to S, must be a final state.

Give the non-empty strings their final state,F.

Then, using input 1, we draw an arrow from state \({{\bf{s}}_0}\) to state\({{\bf{s}}_{\bf{A}}}\), which stands in for the production\({\bf{S}} \to 1{\bf{A}}\). Due to the production rule\({\bf{S}} \to 0\), we also draw an arrow with input 0 from \({{\bf{s}}_0}\) to F.

Then, using input 0, we draw an arrow from state \({{\bf{s}}_{\bf{A}}}\) to state\({{\bf{s}}_{\bf{B}}}\), which stands for the production\({\bf{A}} \to 0{\bf{B}}\). To symbolise the production\({\bf{B}} \to 1{\bf{B}}\), we add a loop with the label 1 to the state\({{\bf{s}}_{\bf{B}}}\).

Finally, we indicate the production \({\bf{B}} \to 1\) by drawing an arrow with input 1 from \({{\bf{s}}_{\bf{B}}}\) to F.

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

So, the result shows that the required nondeterministic finite-state automata.

Construct the nondeterministic finite-state automata

Given,\({\bf{S}} \to 1{\bf{B,S}} \to 0{\bf{,A}} \to 1{\bf{A,A}} \to 0{\bf{B,A}} \to 1{\bf{,A}} \to 0{\bf{,B}} \to 1\)

Construction:

The initial state, \({{\bf{s}}_0}\) , which corresponds to S, is initially drawn.

Let the end state be F.

Then, using input 1, we construct an arrow from state \({{\bf{s}}_0}\) to the production \({\bf{S}} \to 1{\bf{B}}\) state\({{\bf{s}}_{\bf{B}}}\). Due to the production rule\({\bf{S}} \to 0\), we also draw an arrow with input 0 from \({{\bf{s}}_0}\) to F.

Then, using input 0, we draw an arrow from state \({{\bf{s}}_{\bf{A}}}\) to state\({{\bf{s}}_{\bf{B}}}\), which stands for the production\({\bf{A}} \to 0{\bf{B}}\). We also add arrows from \({{\bf{s}}_{\bf{A}}}\)to F with inputs 0 and 1 to represent the productions \({\bf{A}} \to 0\) and\({\bf{A}} \to 1\). We add a loop with label 1 to the state \({{\bf{s}}_{\bf{A}}}\)to represent the production\({\bf{A}} \to 1{\bf{A}}\).

Finally, we indicate the production \({\bf{B}} \to 1\) by drawing an arrow with input 1 from \({{\bf{s}}_{\bf{B}}}\) to F.

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

So, the result shows that the required nondeterministic finite-state automata.