Transform the following grammar into Chomsky normal form S ? baAB|BabA, A ?Aab|B

Question

Explanation / Answer

n computer science, a context-free grammar is said to be in Chomsky normal form if all of its production rules are of the form: A -> BC, or A -> ?, or S -> ? where A, B, C are nonterminal symbols, ? is a terminal symbol, S is the start symbol, and ? is the empty string. Also, neither B nor C may be the start symbol. S0 -> S S -> AB | aB | B A -> aab B -> bbA | bb Instead of using | to denote different choices, split a rule into multiple rules. S0 -> S S -> AB S -> aB S -> B A -> aab B -> bbA B -> bb Create new rules Y -> a and Z -> b because we will need them soon. S0 -> S S -> AB S -> aB S -> B A -> aab B -> bbA B -> bb Y -> a Z -> b S -> aB is not of the form S -> BC because a is a terminal. So change a into Y: S0 -> S S -> AB S -> YB S -> B A -> aab B -> bbA B -> bb Y -> a Z -> b Do the same for the B -> bb rule: S0 -> S S -> AB S -> YB S -> B A -> aab B -> bbA B -> ZZ Y -> a Z -> b For A -> aab, create C -> YY; for B -> bbA, create D -> ZZ: S0 -> S S -> AB S -> YB S -> B A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b For S -> B, duplicate the one rule where S occurs on the right hand side and inline the rule: S0 -> B S0 -> S S -> AB S -> YB A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b Deal with the rules S0 -> B and S0 -> S by joining the right hand side to the left hand sides of other rules. Also, delete the orphaned rules (where the LHS symbol never gets used on RHS): S0 -> DA S0 -> ZZ S0 -> AB S0 -> YB A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.