Theory of Computation
CSE · Quiz · Fall 25
Paper 1 of 3Section 66-ISwitch
Section 66-I
Paper 1 of 3
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Quiz-04-TOC | Section: 66-I
Name: | ID:
Convert this grammar into Chomsky Normal Form (CNF).
S -> AB | BC | aA
A -> BA | a | e
B -> bB | C
C -> AB | b
Your answer must clearly show the following steps:
1. Remove all e-productions
2. Remove all unit productions
3. Remove all useless / non-generating symbols
4. Convert the simplified grammar to proper CNF rules
5. Write the final CNF grammar clearly