# Lower bound for number of nonterminals in a CFG

Let's say we have a context-free grammar for the language $a\mbox{*}b\mbox{*}c\mbox{*}$. Is there a way to determine a lower bound for the number of nonterminals in this grammar? I'm pretty sure you need at least 2, but I haven't been able to prove it.

• What have you tried? You just need to prove that there is no grammar with 1 nonterminal. What form can each rule in such a grammar have? (It's a very restricted form.) Try a case analysis on the different forms such a rule can have. Can you have a rule of the form $S ::= rhs$ where $rhs$ is a string that contains two or more instances of $S$? See also cstheory.stackexchange.com/q/32056/5038 and the questions linked there. – D.W. Dec 31 '15 at 4:02
• That's an interesting complexity measure for context-free languages. Have you done some searching? This may have been studied in the past. – Raphael Dec 31 '15 at 11:42
• Closely related question. Do you guys have the same exercise sheet? – Raphael Dec 31 '15 at 11:44
• @D.W. Is there a relation between the number of states in the pushdown automata and the number of nonterminals in the grammar? – CaptainCodeman Dec 31 '15 at 13:35

You need at least two non-terminals here. For suppose not. A rule of the form $S \to \alpha$ cannot include two copies of $S$, since otherwise it would generate a word of the form $\cdots b \cdots a \cdots$ (since $S$ generates $b,a$). A rule of the form $S \to x S y$ (where $x,y$ are words) cannot mention the letter $b$ for similar reasons. The only rules mentioning $b$ are thus of the form $S \to w$ (where $w$ is a word). It follows that every word generated by the grammar has a bounded number of $b$s (since at most one rule of the form $S \to w$ can be applied when generating a given word), so it doesn't generate all of $a^*b^*c^*$.
In contrast, you can generate the language using two non-terminals: $S \to aS|Sc|B$, $B \to Bb|\epsilon$. Therefore the minimum number of non-terminals needed to generate this language is two.