Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting languages must be simpler, possibly even regular. I don't see how to prove this yet, so can you help me:
Is every context free language equivalent to one whose grammar has only one non-terminal symbol?
Consider the language $L = 0 \cup 1^* = \{0\} \cup \{\varepsilon,1,11,111,\ldots\}$. This is obviously context-free, even regular. However, it cannot be generated by a grammar with only one non-terminal symbol. Assume $G$ would be such a grammar and its only non-terminal symbol is $S$. Since $G$ has only finitely many productions there is some $n$ such that $1^n \in L$ cannot be generated in one step, i.e. it has a derivation $S \Rightarrow^* xSy \Rightarrow^* 1^n$ where $x,y$ are not both empty. Then $x$ and $y$ can cannot contain the symbol $0$. All occurences of $S$ in $x$ and $y$ can be replaced by $1$ as $S \Rightarrow 1$, so we can derive a word $1^aS1^b$ where $a,b$ are not both zero. However, we also have a production $S \rightarrow 0$, so that $G$ also generates the word $1^a01^b$ which is not in $L$; contradiction.
