Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n number of non-terminal to store n states in the NFA?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Closely related question. Do you guys have the same exercise sheet? $\endgroup$– RaphaelCommented Dec 31, 2015 at 11:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No such non-trivial bound can be obtained. Consider the language $L_n = \{ 0^{kn} : k \in \mathbb{N}\}$. Any NFA for $L_n$ needs at least $n$ states, but it can be generated by a context-free grammar with only one non-terminal: $S\to 0^nS|\epsilon$.
answered Dec 31, 2015 at 12:21