Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?

Question

We are given a family of context-free grammars $\{ G_1, G_2, G_3, ..., G_n, ...\}$ where each $G_n$ generates strings only of length $n$ and obeys other constraints specified below. We want to study how corresponding deterministic finite-state automata grow with them.

Specifically, each $G_n = (V_n,\Sigma,R_n,S_n)$ where $V_n$ is the set of non-terminals, and $\Sigma = \{0,1\}$ is the set of terminals. We are also given $c$, $d$, $e$, and $k$ as constants.

Definitions: For this question, let's say that a context-free grammar $G$ is recursive if there is some $N \in V$ and some sequence of derivations from $R$ such that $N \rightarrow^* \cdots N \cdots$, that is, where $N$ appears on the right-hand side of a derivation from $N$. If there is no such $N$, let's call $G$ non-recursive.

Now let's say every $G_n$ is non-recursive and generates strings only of length $n$. We conclude from this that the total language of $G_n$ is finite. For the purposes of this question let's say the grammars are in Chomsky normal form. We are also given that the size of $G_n$ is polynomially bounded, that is, $|V \cup R| = O(n^c)$.

So since each language is finite, we can create a unique minimal deterministic finite-state automaton $A_n=(Q_n,\Sigma,\delta_n,q_{n0},F_n)$ to recognize it. That finite automaton is acyclic.

Questions:

1. Is the number of states in the automaton polynomially bounded, that is, is $|Q_n|=O(n^d)$?
2. Does anything change if we add empty strings to the grammar where there are rules $N \rightarrow \epsilon$ in $R$? Are the number of states in the automaton still polynomially bounded, where $|Q_n|=O(n^e)$?
3. Does anything change if we alter the size of $\Sigma$ such that $|\Sigma|=O(n^k)$? I'm particularly interested in the case where the $i^{th}$ member of $G_n$'s generated output is drawn from a pair. More specifically, we are given $n$ pairs for each $G_n$: $T=\{ \{a_1,b_1\},\{a_2,b_2\},\{a_3,b_3\},...\{a_n,b_n\}\}$. Then each output of $G_n$ is of the form $\sigma_1..\sigma_i...\sigma_n$ where $p_i \in T$ and $\sigma_i \in p_i$.
4. In the domain I’m studying there are no chain rules and only productive non-terminals. I can also say that all the non-terminals are “typed”: they are either lexical categories where either $N_0 \rightarrow \sigma$ where $\sigma \in \Sigma$, or “hierarchical” categories where they take arguments which are lexical categories. So for example, $S \rightarrow N_{01} N_1$, $N_1 \rightarrow N_{02} N_2$, $N_2 \rightarrow N_{03} N_3$. The cases where $N_0 \rightarrow \epsilon$ are there as I understand it to get rid of order problems, so the hierarchical categories and their corresponding lexical categories can be in any order.

My vague idea of how to approach this problem would be to use the Myhill-Nerode theorem to show that for each grammar rule in Chomsky normal form whose right-hand side is composed of two non-terminals, we can observe that the second non-terminal constitutes a similar equivalence class to come after all strings produced by the first non-terminal, and hence merging of states would occur in the minimal automaton. So hopefully the number of states would not multiply, but rather add. But this is about as far as I've gotten.

Answer 1

The sizes $|Q_n|$ can grow exponentially even in the context of question 1 (and thus questions 2 and 3 as well). For $n = 2 k$ even, define the grammar $G_n$ of size $O(n)$ by $$ \begin{align*} S \to {} & S_0 \\ S_i \to {} & 0 S_{i+1} 0 \mathbin{|} 1 S_{i+1} 1 \\ S_k \to {} & \epsilon \end{align*} $$ where $i$ runs from $0$ to $k-1$. There is an equivalent CNF grammar whose size is likewise $O(n)$. Now, $G_n$ generates $L_n = \{ w w^R \;|\; w \in \{0,1\}^k \}$, and it's a standard exercise to prove that the minimal DFA for $L_n$ has at least $2^k$ states.

As for question 4, I don't understand what you mean by "lexical and hierarchical categories" well enough to tell whether these grammars satisfy the condition.