ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

2.7 normal forms cnf & problems

?Download as PPTX, PDF?
?
S
Sampath Kumar S

The document discusses Chomsky Normal Form (CNF) for context-free grammars. A grammar is in CNF if productions are of two forms: A ¡ú BC, with exactly two nonterminals on the right-hand side, or A ¡ú a, with a single terminal. The document outlines a procedure to convert any grammar into CNF by introducing new nonterminals to restrict the number and type of symbols on the right-hand side of productions. Several examples of converting grammars to CNF are provided.

1 of 13
Downloaded 31 times
Chomsky Normal Form (CNF) -Sampath Kumar S, AP/CSE, SECE
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) 11/21/2017 Sampath Kumar S, AP/CSE, SECE 2
Chomsky Normal Form (CNF): ? A CFG is in Chomsky Normal Form (CNF), if each of its production has one of the two forms: 1. NonTerminal ¡ú a string of exactly 2 nonternminals, i.e., A ¡ú BC. 2. 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. 11/21/2017 Sampath Kumar S, AP/CSE, SECE 3
Procedure for converting to CNF: 1. Simplify the CFG (i.e., eliminate null production, unit production and useless symbols). 2. Include the production of the form A¡ú BC|a as it is. 3. 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 Ci for the terminal abc as C1 ¡ú a, C2 ¡ú b, C3 ¡ú c. 11/21/2017 Sampath Kumar S, AP/CSE, SECE 4
Procedure (Cont..,): 4. 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 ¡ú AR1 R1 ¡ú BR2 R2 ¡ú CR3 R3 ¡ú DE Where Ri are the new non-terminals. Note: The language generated by the new CFG is the same as that generated by the original CFG. 11/21/2017 Sampath Kumar S, AP/CSE, SECE 5
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 ¨C Given grammar is in simplified form. Step 2: Identify the production in required form. - A ¡ú b, B ¡ú b are in the required format. 11/21/2017 Sampath Kumar S, AP/CSE, SECE 6
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 ¡ú C2A|C1B A ¡ú C2 AA| C1S|a B ¡ú C1BB| C2S|b C2 ¡ú b C1 ¡ú a . 11/21/2017 Sampath Kumar S, AP/CSE, SECE 7
Problems to discuss: Step 4: Identify the production which is not in CNF format. A ¡ú C2 AA B ¡ú C1BB are not in CNF. So add new nonterminals D & E. S ¡ú C2A|C1B A ¡ú C2 D| C1S|a B ¡ú C1E| C2S|b C2 ¡ú b C1 ¡ú a D ¡ú AA E ¡ú BB This is the required CNF. 11/21/2017 Sampath Kumar S, AP/CSE, SECE 8
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|¦Å 11/21/2017 Sampath Kumar S, AP/CSE, SECE 9
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 11/21/2017 Sampath Kumar S, AP/CSE, SECE 10
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 11/21/2017 Sampath Kumar S, AP/CSE, SECE 11
11/21/2017 Sampath Kumar S, AP/CSE, SECE 13
????? 11/21/2017 Sampath Kumar S, AP/CSE, SECE 14

More Related Content

2.7 normal forms cnf & problems

  • 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) 11/21/2017 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: 1. NonTerminal ¡ú a string of exactly 2 nonternminals, i.e., A ¡ú BC. 2. 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. 11/21/2017 Sampath Kumar S, AP/CSE, SECE 3
  • 4. Procedure for converting to CNF: 1. Simplify the CFG (i.e., eliminate null production, unit production and useless symbols). 2. Include the production of the form A¡ú BC|a as it is. 3. 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 Ci for the terminal abc as C1 ¡ú a, C2 ¡ú b, C3 ¡ú c. 11/21/2017 Sampath Kumar S, AP/CSE, SECE 4
  • 5. Procedure (Cont..,): 4. 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 ¡ú AR1 R1 ¡ú BR2 R2 ¡ú CR3 R3 ¡ú DE Where Ri are the new non-terminals. Note: The language generated by the new CFG is the same as that generated by the original CFG. 11/21/2017 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 ¨C Given grammar is in simplified form. Step 2: Identify the production in required form. - A ¡ú b, B ¡ú b are in the required format. 11/21/2017 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 ¡ú C2A|C1B A ¡ú C2 AA| C1S|a B ¡ú C1BB| C2S|b C2 ¡ú b C1 ¡ú a . 11/21/2017 Sampath Kumar S, AP/CSE, SECE 7
  • 8. Problems to discuss: Step 4: Identify the production which is not in CNF format. A ¡ú C2 AA B ¡ú C1BB are not in CNF. So add new nonterminals D & E. S ¡ú C2A|C1B A ¡ú C2 D| C1S|a B ¡ú C1E| C2S|b C2 ¡ú b C1 ¡ú a D ¡ú AA E ¡ú BB This is the required CNF. 11/21/2017 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|¦Å 11/21/2017 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 11/21/2017 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 11/21/2017 Sampath Kumar S, AP/CSE, SECE 11
  • 12. 11/21/2017 Sampath Kumar S, AP/CSE, SECE 13

Editor's Notes

  • #2: School of EECS, WSU