programming4us
programming4us
DESKTOP

Algorithms for Compiler Design: RIGHT LINEAR AND LEFT LINEAR GRAMMAR

- How To Install Windows Server 2012 On VirtualBox
- How To Bypass Torrent Connection Blocking By Your ISP
- How To Install Actual Facebook App On Kindle Fire
7/24/2010 7:54:17 PM
3.4 RIGHT LINEAR AND LEFT LINEAR GRAMMAR
1 Right Linear Grammar

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

  1. A wB

  2. A w, where A and B are the nonterminals, and w is in T *

Since w is in T *, w can also be a single terminal; hence, every regular grammar, by default, satisfies this requirement of a right linear grammar. Therefore every regular grammar is a right linear grammar. Similarly, when | w | > 1, productions containing w on the right side can be split into more than one production. Each contains only one terminal and only one nonterminal on the right side by using additional nonterminals, because w can be written as ay, where a is the first terminal symbol of w and y is string made of the remaining symbols of w. Therefore, a production A wB can be split into the productions A aB1 and B1 yB without affecting the language generated by the grammar. The production B1 yB can be further split in a similar manner. And this can continue until | y | becomes one. A production A w can also be split into the productions A aB1 and B1 y without affecting the language generated by the grammar. The production B1 y can be further split in a similar manner, and this can continue until | y | becomes one, bringing the productions into the form required by the regular grammar. Therefore, we conclude that every right linear grammar can be rewritten in such a manner; every production of the grammar will satisfy the requirement of the regular grammar. For example, consider the following grammar:

The grammar is a right linear grammar; the production S aaB can be split into the productions S aC and C aB without affecting what is derived from S. Similarly, the production S ab can be split into the productions S aD and D a. The production B bb can also be split into the productions B bE and E b. Therefore, the above grammar can be rewritten as:

which is a regular grammar.

2 Left Linear Grammar

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

  1. A Bw

  2. A w, where A and B are the nonterminals, and w is in T *

For every left linear grammar, there exists an equivalent right linear grammar that generates the same language, and vice versa. Hence, we conclude that every linear grammar (left or right) is a regular grammar. Given a right linear grammar, an equivalent left linear grammar can be obtained as follows:

  1. Obtain a regular expression for the language generated by the given grammar.

  2. Reverse the regular expression obtained in step 1, above.

  3. Obtain the regular, right linear grammar for the regular expression obtained in step 2.

  4. Reverse the right side of every production of the grammar obtained in step 3. The resulting grammar will be an equivalent left linear grammar.

For example consider the right linear grammar given below:

The regular expression for the above grammar is obtained as follows. Replace the by = in the above productions to obtain the equations:

Solving equation (II) gives:

By substituting the value of B in (I), we get:

Therefore, the required regular expression is:

And the reverse regular expression is:

The finite automata accepting the language specified by the above regular expression is shown in Figure 1.

Click To expand
Figure 1: Finite automata accepting the right linear grammar for a regular expression.

Therefore, the right linear grammar that generates the language accepted by the automata in Figure 1 is:

Since C is not useful, eliminating C gives:

which can be further simplified by replacing D in B 1D, using D 0 to give:

Reversing the right side of the productions yields:

which is the equivalent left linear grammar. So, given a left linear grammar, an equivalent right linear grammar can be obtained as follows:

  1. Reverse the right side of every production of the given grammar.

  2. Obtain a regular expression for the language generated by the grammar obtained in step 1, above.

  3. Reverse the regular expression obtained in the step 2.

  4. Obtain the regular, right linear grammar for the regular expression obtained in the step 3.

The resulting grammar will be an equivalent left linear grammar. For example, consider the following left linear grammar:

Reversing the right side of the productions gives us:

The regular expression that specifies the language generated by the above grammar can be obtained as follows. Replace the symbols with "=" symbols in the productions of the above grammar to get the following set of equations:

From equation (II), we get:

Substituting this value in (I) gives us:

Therefore,

and the regular expression is:

The reversed regular expression is:

The finite automata that accepts the language specified by the reversed regular expression is shown in Figure 2.

Click To expand
Figure 2: Transition diagram for a finite automata specified by a reversed regular expression.

Therefore, the regular grammar that generates the language accepted by the automata shown in Figure 2 is:

which can be reduced to:

which is the required right linear grammar.

EXAMPLE 1
Start example

Consider the following grammar to obtain an equivalent left linear grammar.

End example

The regular expression for the above grammar is obtained as follows. Replace the by = in the above productions to obtain the equations:

By substituting (III) in (Il) we get:

Therefore, A = (a | gg)A | g and A = (a | gg)*g. By substituting this value in (I) we get:

And the regular expression is:

Therefore, the reversed regular expression is:

But since (a | gg)* is the same as (gg | a)*, the reversed regular expression is same. Hence, the regular, right linear grammar that generates the language specified by the reversed regular expression is the given grammar itself. Therefore, an equivalent left linear grammar can be obtained by reversing the right side of the productions of the given grammar:


Other  
 
Top 10
- Microsoft Visio 2013 : Adding Structure to Your Diagrams - Finding containers and lists in Visio (part 2) - Wireframes,Legends
- Microsoft Visio 2013 : Adding Structure to Your Diagrams - Finding containers and lists in Visio (part 1) - Swimlanes
- Microsoft Visio 2013 : Adding Structure to Your Diagrams - Formatting and sizing lists
- Microsoft Visio 2013 : Adding Structure to Your Diagrams - Adding shapes to lists
- Microsoft Visio 2013 : Adding Structure to Your Diagrams - Sizing containers
- Microsoft Access 2010 : Control Properties and Why to Use Them (part 3) - The Other Properties of a Control
- Microsoft Access 2010 : Control Properties and Why to Use Them (part 2) - The Data Properties of a Control
- Microsoft Access 2010 : Control Properties and Why to Use Them (part 1) - The Format Properties of a Control
- Microsoft Access 2010 : Form Properties and Why Should You Use Them - Working with the Properties Window
- Microsoft Visio 2013 : Using the Organization Chart Wizard with new data
REVIEW
- First look: Apple Watch

- 3 Tips for Maintaining Your Cell Phone Battery (part 1)

- 3 Tips for Maintaining Your Cell Phone Battery (part 2)
programming4us programming4us
programming4us
 
 
programming4us