Chomsky Normal Form: CSE 211 (Theory of Computation)
Chomsky Normal Form: CSE 211 (Theory of Computation)
Chomsky Normal Form: CSE 211 (Theory of Computation)
Assistant Professor
Department of Computer Science and Engineering
Bangladesh University of Engineering & Technology
Noam Chomsky
Example
Example
S → AB|BC
A → BA|a
B → CC|b
C → AB|a
Example
S → AB|BC
A → BA|a
B → CC|b
C → AB|a
Example
S → AB|BC
A → BA|a
B → CC|b
C → AB|a
Example
S → AB|BC
A → BA|a
B → CC|b
C → AB|a
Example
S → AB|BC
A → BA|a
B → CC|b
C → AB|a
Example
S → AB|BC
A → BA|a
B → CC|b
C → AB|a
Example
Theorem
Any context-free language is generated by a context-free
grammar in Chomsky normal form.
Converting to CNF
Example
A is not reachable
Eliminating -productions
Example
Consider the grammar
Production 2 becomes
Example
Similarly
Example
Consider the grammar
Find the unit pairs. (E, E), (T , T ), (F , F ), (I, I) are unit pairs
by zero steps
Example
Example
Converting to CNF
Example
Example
Example
Example