Question

In Exercises 15-17 construct a regular grammar \({\bf{G = }}\left( {{\bf{V,T,S,P}}} \right)\)that generates the language recognized by the given finite-state machine.

Short answer

Therefore, the required regular grammar for the given figure is \({\bf{S}} \to 0{\bf{A,S}} \to 1{\bf{B,S}} \to 0{\bf{,S}} \to {\bf{\lambda ,A}} \to 0{\bf{B,A}} \to 1{\bf{A,A}} \to 1{\bf{,B}} \to 0{\bf{B,B}} \to 1{\bf{A,B}} \to 1\).

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)\) is made up of an initial or start state \({{\bf{s}}_0}\), a finite set S of states, a finite alphabet of inputs, a transition function f that assigns a subsequent state to every pair of states and input, so that \({\bf{f:S \times I}} \to {\bf{S}}\), and a subset F of S made up of final states (or accepting states).

Regular expressions (Definition): The definition of the regular expressions over the set I is recursive:

A regular expression is the symbol \(\emptyset \);

a regular expression with the symbol \({\bf{\lambda }}\);

whenever \({\bf{x}} \in {\bf{I}}\); the symbol x is a regular expression.

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

Sets that can be represented by regular expressions are known as regular sets.

Theorem 2: If and only if it is a regular set, a set is produced by a regular grammar.

Rules of regular expression represents a set:

\(\emptyset \)represents the string-free set, or the empty set.;

\({\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 sequence of the sets represented both by A and by B;

\(\left( {{\bf{A}} \cup {\bf{B}}} \right)\)represents the combination 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 regular grammar

Given that, the language recognized by the given finite-state machine is shown below.

It is noticed that the given figure contains three states. That is, \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}\) and \({{\bf{s}}_2}\).

Construction:

Let us construct the table for understanding.

In the following table, we enter \({{\bf{s}}_{\bf{j}}}\) in the row \({{\bf{s}}_{\bf{i}}}\) and the columnx if there is an arrow from \({{\bf{s}}_{\bf{i}}}\) to \({{\bf{s}}_{\bf{j}}}\) with the label x.

The initial state is designated as \({{\bf{s}}_0}\), and the ending state is designated as \({{\bf{s}}_1}\).

Create the standard grammar \({\bf{G = }}\left( {{\bf{V,T,S,P}}} \right)\).

The arrows in the provided figure are labelled by the terminal symbols T.

\({\bf{T = }}\left\{ {{\bf{0,1}}} \right\}\)

Let \({\bf{S}}\) be the start symbol. We need two additional non-terminal symbols, A and B, because there are two states in addition to the initial state, \({{\bf{s}}_0}\).

The start symbol, non-terminal symbol, and terminal symbols in T are then contained in the set V.

\({\bf{V = }}\left\{ {{\bf{S,A,B,0,1}}} \right\}\)

Let A represent the state \({{\bf{s}}_1}\) and B stand for the state \({{\bf{s}}_2}\). The start symbol S stands for the start state \({{\bf{s}}_0}\).

If there is a labelled arrow pointing from state u to state v, we add a production \({\bf{U}} \to {\bf{xV}}\)with the symbols U and V standing in for the states u and v.

Add a production \({\bf{V}} \to {\bf{x}}\) if u is a final state and there is an arrow with input x from v to u.

Need to add the production \({\bf{S}} \to {\bf{\lambda }}\) because the start state is also an accepted state.

So, the regular grammar is

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

Hence, the needed regular grammar is

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