patternMinor
Why is the start symbol "not allowed" on the right hand side in Chomsky normal form?
Viewed 0 times
whythehandallowedsymbolsidechomskynormalstartform
Problem
I had a question regarding CNF (Chomsky normal form) in formal language theory.
I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow the start symbol to be on the right hand side of the production. However, I just can't wrap my head around why this is so.
In these cases, they put as the first step of converting a general context-free grammar into CNF to add the production
$$S_0 \rightarrow S$$
but I noticed that in some cases this actually leads to having one more unnecessary production, and in other cases it's impossible to completely remove the start symbol completely from the right hand side of productions (excluding the $S_0 \rightarrow S$ production). Also, the textbook that I'm using (Formal Languages and Automata, 6e - Peter Linz) allows the start symbol to be on the right side of a production.
What's the reason that this production is frowned upon?
Thank you.
I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow the start symbol to be on the right hand side of the production. However, I just can't wrap my head around why this is so.
In these cases, they put as the first step of converting a general context-free grammar into CNF to add the production
$$S_0 \rightarrow S$$
but I noticed that in some cases this actually leads to having one more unnecessary production, and in other cases it's impossible to completely remove the start symbol completely from the right hand side of productions (excluding the $S_0 \rightarrow S$ production). Also, the textbook that I'm using (Formal Languages and Automata, 6e - Peter Linz) allows the start symbol to be on the right side of a production.
What's the reason that this production is frowned upon?
Thank you.
Solution
Recall that in Chomsky normal form, we are allowed productions of three forms:
We have to allow the production $S \to \epsilon$, since otherwise it will be impossible to generate the empty string.
Suppose for a moment that the production $S \to \epsilon$ is absent. Then we have the following very useful property:
If $A \Rightarrow^* w$ then $w \neq \epsilon$.
This comes up in some proofs of the pumping lemma, for example.
If we have the rule $S \to \epsilon$, then we no longer have the property above. However, a similar property holds:
If $A \Rightarrow^* w$ and $A \neq S$ then $w \neq \epsilon$.
This is due to our insistence of not having $S$ on the right-hand side of productions; otherwise we might have rules like $A \to SS$ and then derivations like $A \Rightarrow SS \Rightarrow^* \epsilon$.
If the rule $S \to \epsilon$ is absent, then there is no reason to disallow $S$ on the right-hand side of productions. Indeed, some authors allow $S$ on the right-hand side of productions as long as the production $S \to \epsilon$ is absent.
- Productions of the form $A \to a$.
- Productions of the form $A \to BC$.
- The production $S \to \epsilon$.
We have to allow the production $S \to \epsilon$, since otherwise it will be impossible to generate the empty string.
Suppose for a moment that the production $S \to \epsilon$ is absent. Then we have the following very useful property:
If $A \Rightarrow^* w$ then $w \neq \epsilon$.
This comes up in some proofs of the pumping lemma, for example.
If we have the rule $S \to \epsilon$, then we no longer have the property above. However, a similar property holds:
If $A \Rightarrow^* w$ and $A \neq S$ then $w \neq \epsilon$.
This is due to our insistence of not having $S$ on the right-hand side of productions; otherwise we might have rules like $A \to SS$ and then derivations like $A \Rightarrow SS \Rightarrow^* \epsilon$.
If the rule $S \to \epsilon$ is absent, then there is no reason to disallow $S$ on the right-hand side of productions. Indeed, some authors allow $S$ on the right-hand side of productions as long as the production $S \to \epsilon$ is absent.
Context
StackExchange Computer Science Q#92410, answer score: 7
Revisions (0)
No revisions yet.