1. Lecture # 26 Theory Of Automata By Dr. MM Alam 1
2. Lecture 25 Summary • Regular Grammar conversion to FA • JFLAP Practical demonstration • Elimination of NULL Productions • Elimination of UNIT Productions 2
3. Eliminate Unit Productions EXAMPLE • Consider S → A Ibb A → B Ib B→S|a • Separate the units from the nonunits:. Unit Production Other ones S→ A S → bb 3 A→B A→b
4. Killing Unit Productions S → A Ibb A → B Ib B→S|a S→A gives S→b S→A→B gives S→a A→B gives A→ a A→B→S gives A → bb B→S gives B → bb 4
5. Introduction to Chomsky Normal form If L is a language generated by some CFG, then there is another CFG that generates all the non-ʎ words of L, all of whose productions are of one of two basic forms: Nonterminal.-- string of only Nonterminals or Nonterminal - one terminal 5
6. Introduction to Chomsky Normal form Example 1 • Let start with the CFG: S → X I X2aX2 aSb I b Xl → X2X2 I b X2 → aX2 I aaX1 • After the conversion we have: S → X1 X1 → X 2X 2 S → X2AX 2 X1 → B S → ASB X2 → AX 2 6 S→B X2 → AAX1
7. Introduction to Chomsky Normal form Example 1 • We have not employed the disjunction slash I but instead have written out all the productions separately so that we may observe eight of the form: Nonterminal → string of Nonterminals • and two of the form: Nonterminal → one terminal 7
8. Introduction to Chomsky Normal form EXAMPLE 2 • Why not simply replace all a's in long strings by this Nonterminal? For instance, why cannot S → Na N → alb become S → NN N→a lb What do you think? 8
9. EXAMPLE 2 • The answer is that bb is not generated by the first grammar but it is by the second. • The correct modified form is S → NA N → alb A→a 9
10. Introduction to Chomsky Normal form EXAMPLE 3 • The CFG S → XY X → XX Y → YY Y→a Y→ b • (which generates aa*bb*), 10
11. Introduction to Chomsky Normal form EXAMPLE 3 • With our algorithm, become: S → XY X → XX y → yy X→A Y→ B A→a B→b 11
12. Introduction to Chomsky Normal form EXAMPLE • With our algorithm, become: S → XY X → XX Y → yy X→A Y→ B A→a Needless Unit Productions, wastage of time B→b 12
13. What is Chomsky Normal form? Definition • If a CFG has only production of the form Nonterminal → strings of exactly two nonterminals • Or of the form Noneterminal → one terminal • It is called Chomsky Normal Form 13
14. Chomsky Normal form Example 4 • Let us convert S---> aSa I bSb I a | b I aa I bb • First separate the terminals from the nonterminal as in T S → ASA S → >BSB S → AA S → BB 14
15. Chomsky Normal form Conversion Example 4 • We are careful not to introduce the needless unit productions S → A and S → B. • Now we introduce the R's: S → AR 1 S → AA R 1 → SA S → BB S → BR2 S→a R2 → SB S→b 15
16. Chomsky Normal form Example 5 • Convert the CFG into CNF. S → bA I aB A → bAA | aS | a B → aBB | bS | b • The grammar becomes: S → YA B → XBB S → XB B → YS A → YAA B→ b 16
17. Chomsky Normal form Example 5 • We have left well enough alone in two instances: A → a and B → b • We need to simplify only two productions: A → YAA becomes {A → YR1, R1 →AA} • and B → XBB becomes { B → XR2,R2 → BB} 17
18. Chomsky Normal form Example 5 • The CFG has now become: S → YA I XB A → YR1 | XS | a B → XR2 | YS | b X→a Y→b R1 → AA 18 R2 → BB
19. Chomsky Normal form Example 6 • Consider the CFG S → aaaaS I aaaa • Which generates the language a4n for n = 1 2 3....= {a 4 , a8, a 12 ... } • Convert this to CNF as follows: S → AAAAS S → AAAA 19 A→a
20. Chomsky Normal form Example 6 Which in turn becomes S → AR1 R1 → AR2 R2 → AR3 R3 → AS S → AR4 R4 → AR5 20 R5 → AA