patternModerate
The importance of normal forms like Chomsky normal form for CFGs
Viewed 0 times
theimportancechomskylikenormalforformformscfgs
Problem
I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't understand the need of that.
Why they are important in the theory of languages? All the textbooks I referred to tell about these normal forms but not telling anything about their importance.
Why they are important in the theory of languages? All the textbooks I referred to tell about these normal forms but not telling anything about their importance.
Solution
There are at least two relevant uses.
-
Simplicity of proofs
There are plenty of proofs around context-free grammars, including reducability and equivalence to automata. Those are the simpler the more restricted the set of grammars you have to deal with is. Therefore, normal forms can be helpful there.
As a concrete example, Greibach normal form is used to show (constructively) that there is an $\varepsilon$-transition-free PDA for every CFL (that does not contain $\varepsilon$).
-
Enables parsing
While PDAs can be used to parse words with any grammar, this is often inconvenient. Normal forms can give us more structure to work with, resulting in easier parsing algorithms.
As a concrete example, the CYK algorithm uses Chomsky normal form. Greibach normal form, on the other hand, enables recursive-descent parsing; even though backtracking may be necessary, space complexity is linear.
-
Simplicity of proofs
There are plenty of proofs around context-free grammars, including reducability and equivalence to automata. Those are the simpler the more restricted the set of grammars you have to deal with is. Therefore, normal forms can be helpful there.
As a concrete example, Greibach normal form is used to show (constructively) that there is an $\varepsilon$-transition-free PDA for every CFL (that does not contain $\varepsilon$).
-
Enables parsing
While PDAs can be used to parse words with any grammar, this is often inconvenient. Normal forms can give us more structure to work with, resulting in easier parsing algorithms.
As a concrete example, the CYK algorithm uses Chomsky normal form. Greibach normal form, on the other hand, enables recursive-descent parsing; even though backtracking may be necessary, space complexity is linear.
Context
StackExchange Computer Science Q#10468, answer score: 13
Revisions (0)
No revisions yet.