Question: Convert the following grammar to GNF
0

S => ABA | AB | BA | AA | A | B

A => aA | b

B => bB | b

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014

ADD COMMENTlink
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
0
  • A CFG G = (V, T, R, S) is said to be in GNF if every production is of the form

    A → aα, where a ∈ T and α ∈ V∗

    i.e., α is a string of zero or more variables.

  • Definition: A production U ∈ R is said to be in the form left recursion, if U : A → Aα for some A ∈ V .

  • Left recursion in R can be eliminated by the following scheme:

    a.) If A → Aα1| Aα2 | . . . | Aαr | β1 | β2 | . . . | βs, then replace the above rules by

    • Z → αi | αiZ, 1 ≤ i ≤ r

    • A → βi | βiZ, 1 ≤ i ≤ s

    b.) If G = (V, T, R, S) is a CFG, then we can construct another CFG G1 = (V1, T, R1,S) in Greibach Normal Form (GNF) such that L(G1) = L(G) − {є}

Steps to convert a CFG to GNF

Step1: Rename variables

Let S be $A_1$, A be $A_2$, B be $A_3$

The grammar now becomes

$A_1 =\gt A_1A_2A_3 \ | \ A_2A_3 \ | \ A_3A_3 \ | \ A_2A_2 \ | \ A_2 \ | \ A_3$

$A_2 =\gt aA_2 \ | \ a$

$A_3 =\gt bA_3 \ | \ b$

Step 2: For each $A_i =\gt A_j$, ensure i <= j, which is satisfied in all cases

Step 3: Remove left recursion, which is not seen in this example

Step 4: Get all productions in GNF

Consider

$A_1 =\gt A_1A_2A_3$

$A1 =\gt aA_2A_2A_3 \ (as \ A_2 =\gtaA_2) \ \ is \ a \ GNF$

Consider

$A_1 =\gt A_2A_3$

$A1 =\gt a A_2A_3 \ (as \ A_2 =\gt aA_2) \ is \ a \ GNF$

Consider

$A_1 =\gt A_3A_3$

$A_1 =\gt bA_3A_3 \ (as A_3 =\gtbA_3) \ is \ a \ GNF$

Consider

$A_1 =\gt A_2A_2$

$A_1 =\gt aA_2A_2 \ (as \ A_2 =\gt aA_2) \ is \ a \ GNF$

Consider

$A_1 =\gt A_2$

$A_1 =\gtaA_2 \ (as \ A_2 =\gt aA_2) \ is \ a \ GNF$

Consider

$A_1 =\gt A_3$

$A_1 =\gt bA_3 \ (as \ A_3 =\gtbA_3) \ is \ a \ GNF$

ADD COMMENTlink
written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.