Every grammar in Chomsky Normal is contextfree, and conversely, every contextfree grammar which does not generate the empty string can be transformed into an equivalent one which is in Chomsky Normal Form.
The Chomsky Normal Form of a contextfree grammar is important because it yields efficient algorithms. For example, the CYK algorithm which decides whether a given string can be generated by a given grammar uses the Chomsky Normal Form.
Search Encyclopedia

Featured Article
