Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

CNF from S–>aAD;A->aB/bAB;B->b,D->d.

RGPV 2020   
Find the grammar in Chomsky Normal form equivalent to S–>aAD;A->aB/bAB;B->b,D->d.

Ans. A context free grammar (CFG) is said to be in chomsky normal form (CNF) if all its productions are of the form-
  1. A → BC 
  2. A → a
where A, B, C are non-terminals and a is a terminal.
This CFG S–>aAD;A->aB/bAB;B->b,D->d, can be written as
  1. S –> aAD, Not in CNF
  2. A –> aB, Not in CNF
  3. A –> bAB, Not in CNF
  4. B –> b, In CNF
  5. D –> d, In CNF
  6. E –> a, Generate new production, In CNF
  7. F –> AD, Generate new production, In CNF
  8. G –> AB, Generate new production, In CNF
Select 1 production:
S –> aAD
can be written as 
S –> EAD, (E –> a)
S –> EF, (F –> AD)
Now its in CNF.
Select 2 production:
A –> aB
can be written as
A –> EB, (E –> a)
Now its in CNF.
Select 3 prodcution:
A –> bAB
can be written as
A –> BAB, (B –> b)
A –> BG, (G –> AB)
Now its in CNF.
So, CNF of CFG given in question is:
S –> EF, Not in CNF
A –> EB, Not in CNF
A –> BG, Not in CNF
B –> b, In CNF
D –> d, In CNF
E –> a, Generate new production, In CNF
F –> AD, Generate new production, In CNF
G –> AB, Generate new production, In CNF