Question

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

Short answer

The finite-state automaton produced from a regular grammar in the proof of Theorem 2 recognizes the set created by this grammar 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: A set is formed by a regular grammar if and only if it is a regular set.

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

The combination of the sets that bothA andBrepresent 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:

There is a distinct derivation for each terminal string in the grammar, and this is mirrored in how the machine functions (as each regular sub-expression has a unique machine that was given in the proof).

Additionally, those generated nonempty strings will be carefully guided to the machine's finished 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.