Before starting GNF let we first understand Left recursive grammar:
NOTE: Left recursive grammar
if any grammar is in the form of
A → A α | β than it is a left recursive.
For removing left recursive we can write
A → βB | β
B →αB | α
In general format we can write:
A→ A α1 | A α2 | A α3 ----- | A αn | β1 | β2 ------ | βm
For removing left recursive we can write
A→ β1 B | β2 B |β3 B ----- | βm B | β1 | β2 ------ | βm
B→ α1 B | α2 B | α3 B ----- | αn B | α1 | α2 ------ | αn
GNF (Greibach Normal Form)
Any CFG (Context free Grammar) is in GNF if the production is the following form
A → bα
here :
b → Production start with one terminal
α → String of Non terminal. Like:( C1,C2,C3,..... Cn)
where:
A ∈ V
b ∈ T
α ∈ V*
Example :
1. A → a This is in GNF ; where α ∈ ∈ ( since α ∈ V*) , a ∈ T
2. S → aBC This is in GNF ; where BC ∈ V* , a ∈ T
3. S → aB This is in GNF ; where B ∈ V* , a ∈ T
Example :
S → aB | bA
A → bAA | aS | a
B → aBB | bS | b
where:
V= { S , A , B }
T= {a,b}
S= S (starting symbol)
This example is in GNF form.
Conversion of Grammar into GNF:
1. Only simplified grammar are converted into GNF
Simplified means :
# There is no useless symbols.
# There is no unit production.
# There is no Null Production.
# There is no unreachable production.
# There is no left recursive production.
2. Left Grammar can not be converted into GNF.
Reason:
Left recursive grammar is in the form of A → Aα | β
[Here the starting symbol of the production is a set of variable i.e capital letter but in GNF the starting symbol must be one terminal i.e (small letter).]
Example:
Question 1.
A → aBd
B→ b
This grammar is not in GNF because it does not satisfy GNF conditions.
For Convert into GNF assume and substitute production ( D→d )
Now the grammar become
A → aBD
B→ b
D→d
Now this grammar is in GNF.
Question 2.
A→ab
This grammar is not in GNF
For Convert into GNF assume and substitute production (B→b)
Now the grammar become
A→aB
B→b
Now this grammar is in GNF
Question 3
A→aA | aBa | ba
B→ b
This grammar is not in GNF
For Covert into GNF assume and substitute production (D→a)
Now the grammar is
A→aA | aBD | bD
B→ b
D→ a
Now this grammar is in GNF
Question 4
Convert the following grammar into GNF.
S→AA | 0
A→ SS | 0
Solution:
Here the above grammar is left recursive, so first we remove it.
Substitute production of S in production A
A→ AAS | 0S | 1 (This is in the form of left recursion)
Now here compare with A → A α | β
Where: α =AS , β1=0S , β2=1
So we can write in the form of
A → βB | β
B →αB | α
For removing left recursion.
Now we can write:
A→ 0SB | 1B | 0S | 1
B→ ASB | AS
Now grammar is not in GNF , so we substitute production of A in production B to convert GNF
we get:
B→ 0SBSB | 1BSB | 0SSB | 1SB | 0SBS | 1BS | 0SS | 1S
Now substitute production of A
S→ 0SBA | 1BA | 0SA | 1A | 0
Now the grammar will be:
S→ 0SBA | 1BA | 0SA | 1A | 0
A→ 0SB | 1B | 0S | 1
B→ 0SBSB | 1BSB | 0SSB | 1SB | 0SBS | 1BS | 0SS | 1S
Where:
V = {S,A,B}
T = {0,1}
S=S
Question 5
Convert the following grammar into GNF.
A1→A3 A2 ----------------------(1)
A2→A1 A3 | a ----------------------(2)
A3→A2 A1 | b ----------------------(3)
Solution:
Substitute production of A2 in production (3)
A3→ A1 A3 A1 | a A1 | b ------------------(4)
Substitute production of A1 in production (4)
A3 →A3 A2 A3 A1 | a A1 | b (This is in the form of left recursion)
Now here compare with A → A α | β
Where: α =A2 A3 A1 , β1=a A1 , β2=b
So we can write in the form of
A → βB | β
B → αB | α
For removing left recursion.
Now we can write:
A3→ a A1 B | bB |a A1 | b (Now it is in GNF)
B→ A2 A3 A1 B | A2 A3 A1 ------------------- (5)
Now substitute the production of A3 in (1)
A1→ aA1 B A2 | b B A2 | a A1 A2 | b A2 (Now it is in GNF)
Now substitute the production of A1 in (2)
A2→ a A1 B A2 A3 | b B A2 A3 | a A1 A2 A3 | b A2 A3 | a (Now it is in GNF)
Now Subsitute the production of A2 in (5)
B→ a A1 B A2 A3 A3 A1 B | b B A2 A3 A3 A1 B | a A1 A2 A3 A3 A1 B | b A2 A3 A3 A1 B | a A3 A1 B | a A1 B A2 A3 A3 A1 | b B A2 A3 A3 A1 | a A1 A2 A3 A3 A1 | b A2 A3 A3 A1 | a A3 A1 (Now it is in GNF)
Now the Grammar will be :
A1→ aA1 B A2 | b B A2 | a A1 A2 | b A2
A2→ a A1 B A2 A3 | b B A2 A3 | a A1 A2 A3 | b A2 A3 | a
A3→ a A1 B | bB |a A1 | b
B→ a A1 B A2 A3 A3 A1 B | b B A2 A3 A3 A1 B | a A1 A2 A3 A3 A1 B | b A2 A3 A3 A1 B | a A3 A1 B | a A1 B A2 A3 A3 A1 | b B A2 A3 A3 A1 | a A1 A2 A3 A3 A1 | b A2 A3 A3 A1 | a A3 A1
Where :
V = {A1 , A2 , A3 }
T = {a,b}
S = A1
Question 6
S→ A a | a
A→ Sb | b
Solution:
This grammar is left recursive and not in CNF.
For converting CNF add production ( D1→ a , D2→ b )
we get:
S→AD1 | a ---------------- (1)
A→SD2 | b ---------------- (2)
D1→ a
D2→ b
Substitute production of S in (2)
A→ A D1 D2 | a D2 | b
This production is in left recursion
Now here compare with A → A α | β
Where: α =D1 D2 , β1=a D2 , β2=b
So we can write in the form of
A → βB | β
B → αB | α
For removing left recursion.
Now we can write:
A→ a D2 B | b B | a D2 | b
B→ D1 D2 B | D1 D2 ------------ (3)
Substitute production of A in (1)
S→ a D2 B D1 | a B D1 | a D2 D1 | b D1 | a (Now it is in GNF)
Substitute production D1 in (3)
B→ a D2 | a D2 (Now it is in GNF)
Now the grammar will be :
S→ a D2 B D1 | a B D1 | a D2 D1 | b D1 | a
A→ a D2 B | b B | a D2 | b
B→ a D2 | a D2
D1→ a
D2→ b
No comments:
Post a Comment