Question

Show that a set is generated by a regular grammar if and only if it is a regular set.

Short answer

Therefore, a set is generated by a regular grammar if and only if it is a regular set is proved as true.

Step-by-step solution

General form

Regular expressions (Definition): The definition of a regular expression over a set I is as follows:

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

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

When \(x \in I\) occurs, the symbol x is a regular expression.

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

Regular set: The sets represented by regular expressions are called regular sets.

Regular grammar: a phrase-structure grammar where every production is of the form \(A \to aB,A \to a,\) or \(S \to \lambda ,\) where A and B are nonterminal symbols, S is the start symbol, and a is a terminal symbol.

Step 2: Proof of the given statement

Given that, a regular grammar if and only if it is a regular set.

To prove: a set is generated by a regular grammar if and only if it is a regular set.

Proof:

Part (1):

Let's demonstrate how a set is generated by a regular grammar when it is regular and how it is generated by a regular grammar when it is not regular.

A should be a standard set.

Given that we can transfer all transitions to \({s_0}\) to an additional state \(s_0'\), let \(M\) be a finite-state machine that identifies A such that \({s_0}\) is never the next state for a transition.

If \(G = \left( {V,\,T,\,S,\,P} \right)\) is such that:

The symbol S is represented the start symbol \({s_0}\).

Each state of S and each input symbol of I are given symbols, forming the variable V.

P is created from M’s transitions. When state \({\bf{s}}\) changes to state t with input a and we add a production, \({A_s} \to {A_t}\). In order to determine whether there is a change from state \(s\) to the final state, we add a production \({A_s} \to a\) and input a. When \({s_0}\) is a start state, then we add a production \(S \to \lambda \).