patternMinor
Why add S0 -> S while converting CFG to Chomsky Normal Form
Viewed 0 times
whywhilechomskycfgnormalformconvertingadd
Problem
While converting CFG to CNF sometimes it is suggested to add extra step.
Add new start symbol S0 and add new derivation S0 -> S. Book Hopcroft Ullman does not suggest this step but many other articles suggest to add this step.
What is purpose of adding this extra derivation?
Add new start symbol S0 and add new derivation S0 -> S. Book Hopcroft Ullman does not suggest this step but many other articles suggest to add this step.
What is purpose of adding this extra derivation?
Solution
This has to do with the fact that grammars in Chomsky normal form cannot generate the empty word. Indeed, if we only allow rules of the form $A \to BC$ and $A \to a$, then it is impossible to generate the empty word.
In order to accommodate languages containing the empty word, we allow the transition $S \to \epsilon$, where $S$ is the starting symbol. For various reasons (for example, the proof of the pumping lemma), we still don't want any other symbol to generate the empty word, so we disallow $S$ on the right-hand side.
The transition $S_0 \to S$ allows us to treat $S$ as a normal symbol, that is, to allow it to appear on the right-hand side, even if the grammar generates the empty word.
In order to accommodate languages containing the empty word, we allow the transition $S \to \epsilon$, where $S$ is the starting symbol. For various reasons (for example, the proof of the pumping lemma), we still don't want any other symbol to generate the empty word, so we disallow $S$ on the right-hand side.
The transition $S_0 \to S$ allows us to treat $S$ as a normal symbol, that is, to allow it to appear on the right-hand side, even if the grammar generates the empty word.
Context
StackExchange Computer Science Q#131094, answer score: 2
Revisions (0)
No revisions yet.