2.7 normal forms cnf & problems

what is normal forms?
Chomsky Normal Form (CNF)

1. Chomsky Normal Form (CNF) Sampath Kumar S, AP/CSE, SECE

2. Normal Forms: In CFG at the RHS of production there may be any number of terminals and non-terminals in any combination. We need to normalize such grammar (i.e., we want the grammar in some specific format. There should be a fixed number of terminals or non-terminals, in CFG with some criteria. There are 2important normal forms: Chomsky Normal Form (CNF) Greibach Normal Form (GNF) 8/16/2016 Sampath Kumar S, AP/CSE, SECE 2

3. Chomsky Normal Form (CNF): A CFG is in Chomsky Normal Form (CNF), if each of its production has one of the two forms: NonTerminal → a string of exactly 2 nonternminals , i.e., A → BC. NonTerminal → one terminal, i.e., A → a. In CNF, number of symbols on the RHS of the production is strictly limited. The nature of the symbols on the RHS is also restricted. 8/16/2016 Sampath Kumar S, AP/CSE, SECE 3

4. Procedure for converting to CNF: Simplify the CFG (i.e., eliminate null production, unit production and useless symbols). Include the production of the form A→ BC|a as it is. Eliminate the strings of the terminals on the RHS of the productions, if it exceeds one. The procedure is as follows: Suppose we have the production S → Aabc , where abc are terminals & A is nonterminal, then introduce the nonterminal C i for the terminal abc as C 1 → a, C 2 → b, C 3 → c. 8/16/2016 Sampath Kumar S, AP/CSE, SECE 4

5. Procedure (Cont..,): To restrict the number of variable on the RHS, introduce the new variable and separate them as follows: Suppose we have the production with n nonterminals, as shown below with 5 NT Y → ABCDE Add n-2 new productions, using n-2 new nonterminals and modify the production as follow: Y → AR 1 R 1 → BR 2 R 2 → CR 3 R 3 → DE Where R i are the new non-terminals. Note: The language generated by the new CFG is the same as that generated by the original CFG. 8/16/2016 Sampath Kumar S, AP/CSE, SECE 5

6. Problems to discuss: 94. Convert the following CFG to CNF S → bA|aB A→ bAA|aS|a B → aBB|bS|b Solution: Step1: Simplify the CFG – Given grammar is in simplified form. Step 2: Identify the production in required form. - A → b, B → b are in the required format. 8/16/2016 Sampath Kumar S, AP/CSE, SECE 6

7. Problems to discuss: Step 3: Identify the productions which is not in required form and replace every terminal by a variable [ S → bA|aB A → bAA|aS B → aBB|bS ] S → C 2 A|C 1 B A → C 2 AA| C 1 S|a B → C 1 BB| C 2 S|b C 2 → b C 1 → a . 8/16/2016 Sampath Kumar S, AP/CSE, SECE 7

8. Problems to discuss: Step 4: Identify the production which is not in CNF format. A → C 2 AA B → C 1 BB are not in CNF. So add new nonterminals D & E . S → C 2 A|C 1 B A → C 2 D | C 1 S|a B → C 1 E | C 2 S|b C 2 → b C 1 → a D → AA E → BB This is the required CNF. 8/16/2016 Sampath Kumar S, AP/CSE, SECE 8

9. Problems to discuss: 98. Convert the following CFG to CNF S → AB|aB A→ aBB | ε B → bbA 96. Convert the following CFG to CNF S → ASB| ε A→ aAS|a B → SbS|A|bb 97. Convert the following CFG to CNF S → ASA|aB A→ B|S B → b| ε 8/16/2016 Sampath Kumar S, AP/CSE, SECE 9

10. Problems to discuss: 98. Convert the following CFG to CNF S → AB|Aa A→ aAA|a B → bBB|b 99. Convert the following CFG to CNF S → AB|CA, A → a B → BC|AB, C → aB|b 100. Convert the following CFG to CNF S → 0A|1B|C A → 0S|00 B → 1|A C → 01 8/16/2016 Sampath Kumar S, AP/CSE, SECE 10

11. Problems to discuss: 101 . Convert the following CFG to CNF S → aAbB A→ aA|a B → bB|b 102. Convert the following CFG to CNF S → ABa A→ aab B → Ac 103. Convert the following CFG to CNF S → ε | (S) |SS 8/16/2016 Sampath Kumar S, AP/CSE, SECE 11

12. 8/16/2016 Sampath Kumar S, AP/CSE, SECE 12

13. 8/16/2016 Sampath Kumar S, AP/CSE, SECE 13