HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why add S0 -> S while converting CFG to Chomsky Normal Form

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#131094, answer score: 2

Revisions (0)

No revisions yet.