Scribd
Upload
6 views24 pages

Unit 2 Notes

The document discusses Context-Free Grammars (CFG) and their properties, including derivation methods, elimination of useless symbols, € productions, and unit productions. It explains how to convert CFGs into Chomsky Normal Form (CNF) and provides examples of each process. Additionally, it briefly touches on parsing techniques, specifically top-down and bottom-up approaches.

Uploaded by

joshuaindukuri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views24 pages

Unit 2 Notes

The document discusses Context-Free Grammars (CFG) and their properties, including derivation methods, elimination of useless symbols, € productions, and unit productions. It explains how to convert CFGs into Chomsky Normal Form (CNF) and provides examples of each process. Additionally, it briefly touches on parsing techniques, specifically top-down and bottom-up approaches.

Uploaded by

joshuaindukuri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Context Free Grammars and Languages

This CFL accepts equal number of a’s followed by equal number of b’s

This CFL accepts all strtings consists of equal number of a’s and b’s

Derivation: The derivation of a string from the Start symbol is only a valid string. Derivation is
method of deducing a string is called Derivation,The some of possible strings are :
1. SaB Sab ( Here B is replaced by Bb production)
2. SbA Sba ( Here A is replaced by Aa production)
3. SaB SabS (by BbS) SabaB (by SaB) Sabab (by Bb)

Leftmost and Rightmost Derivation

DERIVATION TREE OR PARSE TREE:


:

1. Eliminate useless symbols from the grammar:

SaS/A/C Aa Baa CaCb

Here C is eliminated because it is not causes for any string SaS/A Aa Baa

B is also a useless symbol. After removing B, the productions are SaS/A, Aa

2. Eliminate useless symbols from the grammar:

SaAa AbBB Bab CaB

All variables are producing strings. In next step, we have to eliminate the useless symbols.

SaAa AbBB Bab CaB


CaB has been removed, because it is not in the derivation.

SaAa AbBB Bab is the solution.

Elimination of € Productions:

1. Reduce the following grammar such that there are no € Productions

SaS/bA, AaA/€

SaS SbA Sb and AaA Aa

2. SAaB/aaB A€ BbbA/€ From this grammar eliminate €-productions and


then eliminate useless symbols
Elimination of € productions.
SAaB/aaB/Aa/aB/aa/a (substitute € for each occurrence of A and B separately)
BbbA/bb
Here A is useless symbol so production of a is eliminated from S and B
The resultant grammar is:
SaaB/Aa/aB/aa/
Bbb

Elimination of Unit Productions:

1. SA/bb AB/b BS/a Here the unit productions are SA, AB, BS
SA gives Sb
SAB gives SB gives Sa
AB gives Aa
SBS gives Abb
BS gives Bbb
BSA gives Bb
The new productions are
Sbb/b/a
Ab/a/bb
Ba/bb/b
Here A and B are useless symbols , the resultant grammar is Sbb/b/a
Convert the following CFG into CNF form

SaAD, AaB/bAB , Bb, Dd

For CFG to be in CNF the productions are of the form: ABC or Aa

In the above given CFG Bb and Dd are in CNF from

SaAD is converted to CNF as follows

SCaAD where Ca a

SCaV1 where V1AD

AaB /bAB is converted to CNF as follows:


ACaB

A bAB is converted as ACbAB where Cbb

ACbV2 where V2 AB

The resultant CNF is

SCaV1

ACaB/CbV2

Caa , Cbb and V1AD, V2AB

Bb

Dd

2
PARSING: TOP-DOWN Vs BOTTOM-UP

You might also like