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

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

Step-by-step solution

General form

A finite-state automaton \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) consists 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 each pair of states and inputs (such 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 regular expressions over set I are defined in a recursive manner as follows:

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

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

When \({\bf{x}} \in {\bf{I}}\) is present, the symbol x is a regular expression.

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

Regular sets are the sets that regular expressions represent.

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;

The string having the symbol x in it is represented by the set\(\left\{ {\bf{x}} \right\}\);

(AB) depicts the order of the sets that are represented by both A and B;

The combination of the sets that both A and B represent is represented by \(\left( {{\bf{A}} \cup {\bf{B}}} \right)\);

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

Step 2: Construct the regular grammar

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

The given figure contains three states. That is, \({{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{1}}}\) and \({{\bf{s}}_{\bf{2}}}\).

Construction:

Let us construct the table for understanding.

In the following table, it enters \({{\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}\).

It must 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.

So, the regular grammar is \({\bf{S}} \to 0{\bf{A,S}} \to 1{\bf{B,S}} \to 0{\bf{,A}} \to 0{\bf{B,A}} \to 1{\bf{B,B}} \to 0{\bf{B,B}} \to 1{\bf{B}}\).

Hence, the needed regular grammar is

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