Question

Show that the regular grammar constructed from a finite-state automaton in the proof of Theorem 2 generates the set recognized by this automaton.

Short answer

The regular grammar produced from a finite-state automaton recognizes the set created by this automaton is proved as true.

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 an initial or start state \({{\bf{s}}_0}\), a finite set S of states, a finite alphabet of inputs I, 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):A recursive definition of the regular expressions over a set I is as follows:

A regular expression with 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.

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 Aand B;

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

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

Step 2: Proof of the given statement

Given that, the proof of Theorem 2.

To prove: The set produced by this grammar is recognised by the finite-state automaton created from a regular grammar.

Proof:

Every terminal string in the automaton has a distinct derivation, which is reflected in the construction of the regular gramme as well (because each regular sub-expression has a distinct machine that was provided in the proof).

Likewise, the automaton generates those nonempty strings that will be driven to the machine's final state.

The start state is turned into a final state, and the empty string will only be recognised if it is also included in the language. With the exception of \({\bf{1*}}\), which has the empty string \({\bf{\lambda }}\) as its final state, none of the other submachines mentioned in the proof have the start state as a final state.

Hence, the statement is proved as true.