Greibach Normal Form

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. apply substitution rule 4. eliminate left recursion. 5. check if all productions are in GNF. 3.

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 ,

Which is in GNF.

Bb

EXAMPLE 3  Convert the    

grammar SAB ABS | a BSA | b into GNF.

 SOLUTION:

APPLICATIONS

THANK YOU…