There are two normal forms of every Grammar.
Chomsky Normal Form (CNF) :
A Grammar is in chomsky normal form.
If all production of that grammar should be of the form.
A→ BC or A → a
where : A , B , C is a member of variable.
(A , B , C) ∈ V
a ∈ T
Example :
S → AA | 0
A → SS | 1
Where :
V = { S , A }
T ={ 0, 1 }
S = S
This grammar is in form of (CNF).
Conversion of Grammar into CNF :
CASE 1:
Let A→ a B is any production it is not in CNF form because it does not satisfy CNF condition. So assume any variable for terminal (a).
we get ,
A → DB
D → a
Now it is in CNF form.
CASE 2:
Let A → BCD is any production it is not in CNF form because it has three variables which is not allowed in CNF. So we can assume any variable for BC or CD.
we get ,
A → ED
E → BC
or
A → BE
E → CD
Now both are in CNF form
Let A → ab is any production it is not in CNF form because it has two terminals but in CNF only one terminal are permitted. So suppose any two variable for these terminals.
A → D1 D2
D1 → a
D2 → b
Now it is in CNF
CASE 4:
Let A → aB
B → b
D → a
be any production. It is not in CNF. In this production there is two definition for one terminal which is not possible. So if we write like
A → DB
B → b
D → a
Now it is in CNF.
CASE 5 :
Suppose
Question 1: Conversion of Grammar to CNF:
S → aB | bA
A → bAA | aS | a
B → aBB | bS | b
Solution :
Step 1: Substitute or Replace
D1 → a , D2 → b than grammar become
S → D1 B | D2 A
A → D2 AA | D1 S | a
B → D1 BB | D2 S | b
D1 → a
D2 → b
Step 2: Substitute or Replace
D3 → D1 B , D4 → D2 A than grammar become
S → D1 B | D2 A
A → D4 A | D1 S | a
B → D3 B | D2 S | b
D1 → a
D2 → b
D3 → D1 B
D4 → D2 A
Now it is in CNF
Where:
V = { S , A , B , D1 , D2 , D3 , D4 }
T = { a , b }
S = S
P =
S → D1 B | D2 A
A → D4 A | D1 S | a
B → D3 B | D2 S | b
D1 → a
D2 → b
D3 → D1 B
D4 → D2 A
NULL Production :
∈ (Epsilon)
If A → ∈ is any production is called NULL production.
NULL is not a member of 1.
where T is Terminal.
UNIT Production :
If A → B is any production where A, B ∈ V then this production is called unit production.
Note:
A → b is not unit production
A → aB is also not unit production.
Simplification of Grammar :
Simplification means we make grammar simple.
For making Grammar Simple :
1. Removal of useless symbol / production.
2. Removal of unit production.
3. Removal of NULL production.
Note : It is not possible to convert unit production into CNF | GNF.
Removal of useless symbol / production :
Useless symbol or production are those variable / production which do not terminals.
Example:
S → AB | AC → terminal
B → AB | BC → B is not terminal
A → a → terminated
C → d → terminated
Those production which contain useless symbol are called useless production.
Algorithm for Removal of useless symbol :
Consider a Grammar.
G = ( V , T ,P , S )
which contain useless symbol we have to construct a Grammar.
G' = ( V' , T ,P' , S )
equivalent to G but does not contains useless symbol as follows.
Step 1: Remove all those production from P which contain useless symbol.
P is set of production of G
Step 2: Remove the production of all those variable which are unreachable.
example : A → aB
B → b
C → d → unreachable
C is unreachable so remove it
we get : A → aB
B → b
Step 3: Now initialize P' by all the remaining production.
Example : Remove useless symbol for this grammar.
S → AB | AC
B → AB | BC
A → a
C → d
Solution :
Step 1: Remove all those production from P which contain useless symbol.
S → AC
A → a
C → d
Step 2: Remove the production of all those variable which are unreachable
here no unreachable variable are present.
S → AC
A → a
C → d
Step 3: Now initializing P' by all the remaining production.
V = { S , A , C }
T ={a , d }
S = S
Removal of unit production:
If A → B is any production where A , B ∈ V .
Algorithm for Removal for unit Production :
It has two parts
1. Algorithm 1: Find the set of A - derivable where A ∈ V
Ex: A → B i.e B is a derivable.
Step 1: If A → B be any production where A , B ∈ V then B is A derivable.
Step 2 : If A → B and B → C be any production
where A,B,C ∈ V Then C is A - derivable (by transition property)
Step 3: Variable obtained from step 1 and step 2 are added in the set of A - derivable.
A - derivable = { B , C }
Ex: E → E + T | T
T → T * F | F
F → (E) | id
E → derivable { T ,F } [since E→T, T→F than E→F]
T → derivable { F }
F → derivable { φ }
2. Algorithm 2: Removal of Unit Production:
Consider a grammar G =(V,T,P,S) which contain unit productions. We have to construct a grammar.
G' = (V' , T , P' , S )
which has no unit production but equivalent to G as follows:
Step 1: Find the set of A- derivable for every A ∈ V using algorithm 1.
Step 2: Construct every possible ordered pair (A,B)
Ordered → Two related elements.
where B is A - derivable.
Ex: E = { T , F }
(E , T ) , ( E , F ) ordered pair.
Step 3: For every ordered pair (A,B) where B is A - derivable ADD to A all non-unit production of B.
Step 4: Remove all unit production and initialize P' by all remaining production.
Example : Remove unit production of following grammar.
E → E * T | T
T → T* F | F
F → (E) | id
Step 1: Find the set of A - derivable for every A ∈ V.
E - derivable {T,F}
T - derivable { F}
F - derivable { φ}
Step 2: Construct every possible ordered pair.
( E , T) ( E , F) ( T , F )
Step 3: For every ordered pair (A,B) where B is A - derivable add to A all non - unit production of B.
i. (E , T)
E → E + T | T | T * F
T → T * F | F
F → (E) | id
ii. (E , F)
E → E + T | T | T * F | (E) | id
T → T*F | F
F → (E) | id
iii. (T , F)
E→E + T | T | T * F | (E) | id
T→ T* F | F | (E) | id
F→ (E) | id
Step 4: Remove all the unit productions and initialize P' by all remaining production.
E→E + T | T | T * F | (E) | id
T→ T* F | F | (E) | id
F→ (E) | id
where:
V = { E , T , F }
T = { + , * , ( , ) , id }
S = E
Removal of NULL Production:
If A → ∈ (epsilon) is any production where A ∈ V then production is called NULL Production.
Algorithm for removal of NULL production:
It has two parts:
1. Algorithm 1: Find the set of Null able variables.
(variable which derive NULL are called Null able variables)
Step 1: If A → ∈ be any production where A ∈ V then A is Null able.
Step 2: If A → B and B→ ∈ are production where A,B ∈ V than A → ∈ (by transition property)
i.e A is Null able.
Step 3: If A →B1, B2, B3, .... Bn be any production where
A1,B1,B2 ... Bn ∈ V
and B1,B2,.... Bn all are Null able than
A is null able ( all right hand side variable are null able )
Step 4: Variable obtain from step 1,2 and 3 are added in set of null able.
2. Algorithm 2: Removal of NULL Production:
Consider a grammar G = { V , T , P , S } which contain NULL production we have to construct a grammar.
G' = { V' , T , P' , S }
equivalent to G but does not contains NULL production as follows.
Step 1: Initialize P' as P
( Transfer all the production of P to P' )
Step 2: Find the set of null able variable using Algorithm 1.
Step 3: For any production A → α (alpha) in P add to P'. All production that can be obtained from this by deleting from any subset (sub string) of the occurrence in ( α ) of null able variable.
Ex: If any production is
A → aB
B → b | ∈
than we can write
A → aB | a
B → b | ∈
Ex: If any production is
A → aBC | aC
B → b | ∈
C → d | ∈
than we can write
A → aBC | aC |aB| a | a
B → b | ∈
C → d | ∈
Step 4: Remove all NULL production or duplicate production and remove production of the form.
Ex: If any production is
A → aBC | aC | aB| a | a
B → b | ∈
C → d | ∈
than we can write
A → aBC | aC | aB| a
B → b
C → d
Example 1 : Remove NULL production from the following grammar:
P =
S → ABA
A → aA | ∈
B→ bB | ∈
Solution:
Step 1: Initialize P' to P
P' =
S → ABA
A → aA | ∈
B→ bB | ∈
Step 2: Find set of null able variables.
Null able variables are { S , A , B }
Step 3:
S → ABA |BA|AB|AA|A|B
A → aA | ∈ | a
B→ bB | ∈ | b
Step 4: In this step all the epsilon are removed
S → ABA |BA|AB|AA|A|B
A → aA | a
B→ bB | b
where :
V ={ S , A , B }
T = { a , b }
S = S
Example 2 : Simplify the following grammar:
P=
S → aSa | bSb | A
A → aBb | bBa
B → aB | bB | ∈
Solution:
S → aSa | bSb | A
A → aBb | bBa
B → aB | bB | ∈
Step 1: Remove useless production. Here no useless production are there.
Step 2: Removal Null production.
i. Null able variable are {B}
ii. S → aSa | bSb | A
A → aBb | bBa | ab | ba
B → aB | bB | ∈ | a | b
Step 3:
S → aSa | bSb | A
A → aBb | bBa | ab | ba
B → aB | bB | a | b
So,
P' =
S → aSa | bSb | A
A → aBb | bBa | ab | ba
B → aB | bB | a | b
where:
V = { S , A , B }
T = { a ,b }
S =S
Example 3: Simplify the following grammar:
P=
S → AB
A → a
B→ C | b
C → D
D→ E
E→a
Solution:
Remove unit production
i. First find set of derivable
B - derivable { C , D , E }
C - derivable { D , E }
D - derivable { E }
Possible set of derivable:
(B,C) (B,D) (B,E) (C,D) (C,E) (D,E)
For (B,C)
S → AB
A → a
B→ C | b
C → D
D→ E
E→a
For (B,D)
S → AB
A → a
B→ C | b
C → D
D→ E
E→a
For (B,E)
S → AB
A → a
B→ C | b | a
C → D
D→ E
E→a
For (C,D)
S → AB
A → a
B→ C | b | a
C → D
D→ E
E→a
For (C,E)
S → AB
A → a
B→ C | b | a
C → D | a
D→ E
E→a
For (D,E)
S → AB
A → a
B→ C | b | a
C → D | a
D→ E |a
E→a
Remove those production which are repeatable such as
B→ C|b|a
here C→ a and B→a
i.e B→a|b|a here a is twice so remove it in all production.
S → AB
A → a
B→ b | a
C → a
D→ a
E→a
Remove unreachable productions.
S → AB
A → a
B→ b | a
Where;
V = { S , A ,B }
T = { a , b }
S = S
Example 4: Remove unit production from the grammar whose production rule is given by
P=
S → AB
A → 0
B → C |1
C → D
D → E
E → 0
Solution :
In the above production unit productions are:
B → C
C → D
D → E
Now we remove the unit production
For production ( D → E )
we can write D → 0 , Since E→ 0
so we add D → 0
Now the production are:
S → AB
A → 0
B → C |1
C → D
D → 0
E → 0
For production ( C → D )
we can write C → 0 Since D→0
So we add C → 0
Now the production are:
S → AB
A → 0
B → C |1
C → 0
D → 0
E → 0
For production ( B → C )
we can write B → 0 Since C → 0
So we add B → 0
Now the production are:
S → AB
A → 0
B → 0 |1
C → 0
D → 0
E → 0
Now here C,D,E are unreachable symbol , so we remove it from production.
So the final production are
S → AB
A → 0
B → 0 |1
Example 5: Remove unit production from the grammar whose production rule is given by
P=
S → aX | bY | Z
X → aS | aa
Y → a | X
Z → ab
Example 6: Remove unit production from the grammar whose production rule is given by
P=
S → Xa | Y
Y → X | bb
X → a | bc | Y
No comments:
Post a Comment