3.4 RIGHT LINEAR AND LEFT LINEAR GRAMMAR | Algorithms for Compiler Design (Electrical and Computer Engineering Series)

3.3 REGULAR GRAMMAR

Regular grammar is a context-free grammar in which every production is restricted to one of the following forms:

A ’ aB , or
A ’ w , where A and B are the nonterminals , a is a terminal symbol, and w is in T *.

The ˆˆ - productions are permitted as a special case when L ( G ) contains ˆˆ . This grammar is called "regular grammar," because if the format of every production in CFG is restricted to A ’ aB or A ’ a , then the grammar can specify only regular sets. Hence, a finite automata exists that accepts L ( G ), if G is regular grammar. Given a regular grammar G , a finite automata accepting L ( G ) can be obtained as follows :

The number of states of the automata will be equal to the number of nonterminals of the grammar plus one; that is, there will be a state corresponding to every nonterminal of the grammar. And one more state will be there, which will be the final state of the automata. The state corresponding to the start symbol of the grammar will be the initial state of the automata. If L ( G ) contains ˆˆ , then make the start state also the final state.
The transitions in the automata can be obtained as follows:
- for every production A ’ aB do
  
  for every production of the form A ’ a do

EXAMPLE 3.13

Consider the regular grammar shown below and the transition diagram of the automata, shown in Figure 3.7, that accepts the language generated by the grammar.

Figure 3.7: Transition diagram for automata that accepts the regular grammar of Example 3.13.

This is a non-deterministic automata. Its deterministic equivalent can be obtained as follows:

		1
{ S }	{ A, C }	{ B, C }
*{ A, C }	{ S }	{ B, C }
*{ B, C }	{ A }	{ S }
{ A }	{ S }	{ B, C }

The transition diagram of the automata is shown in Figure 3.8.

Figure 3.8: Deterministic equivalent of the non-deterministic automata shown in Figure 3.7.

Consider the following grammar:

The transition diagram of the finite automata that accepts the language generated by the above grammar is shown in Figure 3.9.

Figure 3.9: Non-deterministic automata.

This is a non-deterministic automata. Its deterministic equivalent can be obtained as follows, and the transition diagram is shown in Figure 3.10.

Figure 3.10: Transition diagram for deterministic automata equivalent shown in Figure 3.9.

Given a finite automata M , a regular grammar G that generates L ( M ) can be obtained as follows:

Associate suitable variables like A, B, C, etc, with the states of the automata. The labels of the states can also be used as variable names .
Obtain the productions of the grammar as follows. If ( A , a ) = B , then add a production A ’ aB to the list of productions of the grammar. If B is a final state, then add either A ’ a or B ’ ˆˆ , to the grammar's list of productions.
The variable associated with the initial state of the automata is the start symbol of the grammar.

For example consider the automata shown in Figure 3.11.

Figure 3.11: Regular-grammar automata.

The regular grammar that generates the language accepted by the automata shown in Figure 3.11 will have the following productions:

where A is the start symbol. Both the grammars are same, but the first one contains ˆˆ -productions, whereas the second is ˆˆ -free.

EXAMPLE 3.14

Find out whether the following grammar generates the same language.

G ₁ :

G ₂ :

Since the grammars G ₁ and G ₂ are the regular grammars, L ( G ₁ ) = L ( G ₂ ) if the minimal state automata accepting L ( G ₁ ), and the minimal state automata accepting L ( G ₂ ) are identical. The transition diagram of the automata accepting L ( G ₁ ) is shown in Figure 3.12.

Figure 3.12: Transition diagram of automata that accepts L ( G ₁ ).

The automata is deterministic. Hence, to minimize, it we proceed as follows. Since state D is an unreachable state, eliminate it first. So, after eliminating state D , we get the transition diagram shown in Figure 3.13.

Figure 3.13: Transition diagram of automata after removal of state D.

We then identify the nondistinguishable states of the automata shown in Figure 3.13, as follows. Initially, we have two groups:

Since

state B is distinguishable from rest of the members of Group I. Hence, we divide Group I into two groups ”one containing A , and other containing E and C , as shown below:

Since

partitioning of Group II is not possible, because the transitions from all the members of Group II only go to Group II. Similarly:

Partitioning of Group II is not possible, because the transitions from all the members of Group II only go to Group I. And since:

partitioning of Group III is not possible, because the transitions from all the members of Group III only go to Group I. Similarly:

Partitioning of Group III is not possible, because the transitions from all the members of Group III only go to Group III. Hence, states E and C are nondistinguishable states. States B and F are also nondistinguishable states. Therefore, if we merge E and C to form a state E ₁ , and we merge B and F to form B ₁ , we get the automata shown in Figure 3.14.

Figure 3.14: Transition diagram for the automata that results from merged states.

Since no dead states exist in the automata shown in Figure 3.14, it is a minimal state automata that accepts L ( G ₁ ). The transition diagram of the non-deterministic automata that accepts L ( G ₂ ) is shown in Figure 3.15.

Figure 3.15: Non-deterministic automata that accepts L ( G ₂ ).

Its equivalent deterministic automata is as follows, and the transition diagram is shown in Figure 3.16.

		1

{ X }	{ Y , F }	{ Z }
*{ Y , F }	{ X }	{ Y , F }
{ Z }	{ Z }	{ X }

Figure 3.16: Transition diagram of the equivalent deterministic automata for Figure 3.15.

This automata does not contain unreachable, nondistinguishable states or dead states. Hence, it is a minimal state automata accepting L ( G ₂ ), and since it is identical to the minimal state automata accepting L ( G ₁ ), L ( G ₂ ) = L ( G ₂ ); and therefore, G ₁ and G ₂ generate the same language.

Obtaining a Regular Expression from the Regular Grammar

Given a regular grammar G , a regular expression that specifies L ( G ) can be directly obtained as follows:

Replace the " ’ " symbols in the grammar's productions with "=" symbols to get a set of equations.
Solve the set of equations obtained above to obtain the value of the variable S , where S is the start symbol of the grammar. The result is the regular expression specifying L ( G ).

For example consider the following regular grammar:

Replacing the " ’ " symbol in the productions of the grammar with the "=" symbol, we get the following set of equations:

From equation (III) we get:

because equation (III) is of the form A = aA b , where a and b are the expressions that do not contain variable A , and the solution of this is A = a * b . Similarly, from equation (II) we get:

Substituting the values of A in (I) gives:

Hence, the required regular expression is: