Scribd
Upload
7K views16 pages

Greibach Normal Form

The document discusses Greibach Normal Form (GNF) for context-free grammars. It states that for a context-free grammar to be in GNF, all productions must be of the form A->aX, where A and X are variables and a is a terminal symbol. The document provides an algorithm to convert any context-free grammar without empty productions to an equivalent grammar in GNF. The algorithm involves eliminating useless/empty variables and productions, converting to Chomsky Normal Form, and then applying substitution rules to move terminals to the leftmost position. Examples of converting grammars to GNF are also given.

Uploaded by

api-3828940
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
7K views16 pages

Greibach Normal Form

The document discusses Greibach Normal Form (GNF) for context-free grammars. It states that for a context-free grammar to be in GNF, all productions must be of the form A->aX, where A and X are variables and a is a terminal symbol. The document provides an algorithm to convert any context-free grammar without empty productions to an equivalent grammar in GNF. The algorithm involves eliminating useless/empty variables and productions, converting to Chomsky Normal Form, and then applying substitution rules to move terminals to the leftmost position. Examples of converting grammars to GNF are also given.

Uploaded by

api-3828940
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 16

GREIBACH NORMAL

FORM
Presented by:-
NEHA JAIN
II-CSE
399/05
GREIBACH NORMAL FORM
 IN CNF we put restrictions on the length of
the right sides of a production.
ABC
Aa
Where A,B,C are in V, and a is in T.

 In GNF restrictions are placed on positions


in which terminals and variables can
appear.
DEFINITION
 A context-free
grammar is said to be in
Greibach Normal Form if all productions
have the form
Aax
Where a є T
And x є V*
THEOREM
 For every context-free grammar G without

λ ε L(G),
There exists an equivalent grammar Ĝ
In
Greibach Normal Form
CONVERSION OF CFG TO GNF
 Starting with a grammar: G = ( V, T, P, S)
 1a) Eliminate useless variables that can not
become terminals
 1b) Eliminate useless variables that can not be
reached
 2) Eliminate epsilon productions
 3) Eliminate unit productions
 4) Convert productions to Chomsky Normal
Form
 5) Convert productions to Greibach Normal
Form using algorithm
STEP 1
 Every CFG must be in CNF form, if not
then convert it into CNF.

 Now rename all variables (V) by A1, A2,….


An where A1 is the start symbol.
STEP 2
 Now modify the grammar so that every
production are of the following form:
 Aa γ
 or AAj γ
where j>I and γ єV*
STEP 2 (..contd)
 To get a CNF in the above discussed format, we should follow the
method:
 Start with A1 and proceed to An. Suppose
upto Am-1 the above condition 1<= i<= (m-1), Ai Aj γ then j>i is
satisfied and for Am we have the production Am  Aj γ such that
j<m.
 To convert production so that is satisfy the above condition we apply
the substitute rule.
 By repeating the process at most m-1 times,we obtain productions
of the form
Am  Apγ where p>=m
 If m=p, we have in left recursive form, which is then
replaced by the method of elimination of left recursion
introducing a new variable Bm
STEP 3
 Since An is the highest numbered variable then
productions are of the form An  aγ .
 Νοω, the leftmost symbol of right side of
any production for An must be either
terminal or Am.
 Replace Am on right side of production Am-1
by replacement rule.
 Now leftmost symbol of the right hand side
of productions for Am-1 is terminal. Repeat this
process for Am-2 Am-3….. A1. now R.H.S. of each
production for an Ai starts with a terminal
symbol.
STEP 4
 The new variables Bi introduced to
eliminate left recursion in step 2 have to
be simplified such that all productions are
of the form in GNF.
 This is done by substitution rules.
 No Bi production can start with another Bj
 Finally combining all productions we get
the required grammar in GNF.
Finally…
 The net conclusion is simple.

3. apply substitution rule


4. eliminate left recursion.
5. check if all productions are in GNF.
EXAMPLE 1
 CONVERT THE GRAMMAR
SAB | BC
A aB | bA | a
BbB | cC | b
Cc into GNF.
 Here the production SAB | BC is not in GNF.
On applying the substitution rule we immediately
get equivalent grammar in GNF.
SaBB | bAB | aB | bBC | cCC | bC
EXAMPLE 2
 CONVERT THE GRAMMAR
S abaSa | aba Into GNF.
 If we introduce new variables A and B and
productions as
 Aa , Bb and substitute into the given
grammar as
 S aBASA | ABA
 Aa , Bb

 Which is in GNF.
EXAMPLE 3
 Convert the
grammar
 SAB
 ABS | a
 BSA | b
 into GNF.

 SOLUTION:
APPLICATIONS
THANK YOU…

You might also like