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.
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ 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. $\endgroup$– D.W. ♦Commented Dec 31, 2015 at 4:02
-
$\begingroup$ That's an interesting complexity measure for context-free languages. Have you done some searching? This may have been studied in the past. $\endgroup$– RaphaelCommented Dec 31, 2015 at 11:42
-
$\begingroup$ Closely related question. Do you guys have the same exercise sheet? $\endgroup$– RaphaelCommented Dec 31, 2015 at 11:44
-
$\begingroup$ @D.W. Is there a relation between the number of states in the pushdown automata and the number of nonterminals in the grammar? $\endgroup$– CaptainCodemanCommented Dec 31, 2015 at 13:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Dec 31, 2015 at 12:28
-
1$\begingroup$ It seems like you have a proof in mind. Write down the proof in complete detail, and see if it works. If it doesn't, try to correct it. You don't need me in order to do all that. $\endgroup$ Commented Dec 31, 2015 at 22:38