Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.