<p>The sizes <span class="math-container">$|Q_n|$</span> can grow exponentially even in the context of question 1 (and thus questions 2 and 3 as well).
For <span class="math-container">$n = 2 k$</span> even, define the grammar <span class="math-container">$G_n$</span> of size <span class="math-container">$O(n)$</span> by
<span class="math-container">$$
\begin{align*}
S \to {} &amp; S_0 \\
S_i \to {} &amp; 0 S_{i+1} 0 \mathbin{|} 1 S_{i+1} 1 \\
S_k \to {} &amp; \epsilon
\end{align*}
$$</span>
where <span class="math-container">$i$</span> runs from <span class="math-container">$0$</span> to <span class="math-container">$k-1$</span>.
There is an equivalent CNF grammar whose size is likewise <span class="math-container">$O(n)$</span>.
Now, <span class="math-container">$G_n$</span> generates <span class="math-container">$L_n = \{ w w^R \;|\; w \in \{0,1\}^k \}$</span>, and it's a standard exercise to prove that the minimal DFA for <span class="math-container">$L_n$</span> has at least <span class="math-container">$2^k$</span> states.</p>
<p>As for question 4, I don't understand what you mean by &quot;lexical and hierarchical categories&quot; well enough to tell whether these grammars satisfy the condition.</p>

CC BY-SA 4.0
2021-09-07T20:20:50.210Z
2021-09-08T06:15:43.343Z
2021-09-08T06:15:43.343Z
Ilkka Törmä
<p>We are given a family of <a href="https://en.wikipedia.org/wiki/Context-free_grammar" rel="nofollow noreferrer">context-free grammars</a> <span class="math-container">$\{ G_1, G_2, G_3, ..., G_n, ...\}$</span> where each <span class="math-container">$G_n$</span> generates strings only of length <span class="math-container">$n$</span> and obeys other constraints specified below. We want to study how corresponding deterministic finite-state automata grow with them.</p>
<p>Specifically, each <span class="math-container">$G_n = (V_n,\Sigma,R_n,S_n)$</span> where <span class="math-container">$V_n$</span> is the set of non-terminals, and <span class="math-container">$\Sigma = \{0,1\}$</span> is the set of terminals. We are also given <span class="math-container">$c$</span>, <span class="math-container">$d$</span>, <span class="math-container">$e$</span>, and <span class="math-container">$k$</span> as constants.</p>
<p>Definitions: For this question, let's say that a context-free grammar <span class="math-container">$G$</span> is <em>recursive</em> if there is some <span class="math-container">$N \in V$</span> and some sequence of derivations from <span class="math-container">$R$</span> such that <span class="math-container">$N \rightarrow^* \cdots N \cdots$</span>, that is, where <span class="math-container">$N$</span> appears on the right-hand side of a derivation from <span class="math-container">$N$</span>. If there is no such <span class="math-container">$N$</span>, let's call <span class="math-container">$G$</span> <em>non-recursive</em>.</p>
<p>Now let's say every <span class="math-container">$G_n$</span> is non-recursive and generates strings only of length <span class="math-container">$n$</span>. We conclude from this that the total language of <span class="math-container">$G_n$</span> 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 <span class="math-container">$G_n$</span> is polynomially bounded, that is, <span class="math-container">$|V \cup R| = O(n^c)$</span>.</p>
<p>So since each language is finite, we can create a unique minimal <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton" rel="nofollow noreferrer">deterministic finite-state automaton</a> <span class="math-container">$A_n=(Q_n,\Sigma,\delta_n,q_{n0},F_n)$</span> to recognize it. That finite automaton is acyclic.</p>
<p>Questions:</p>
<ol>
<li>Is the number of states in the automaton polynomially bounded, that is, is <span class="math-container">$|Q_n|=O(n^d)$</span>?</li>
<li>Does anything change if we add empty strings to the grammar where there are rules <span class="math-container">$N \rightarrow \epsilon$</span> in <span class="math-container">$R$</span>? Are the number of states in the automaton still polynomially bounded, where <span class="math-container">$|Q_n|=O(n^e)$</span>?</li>
<li>Does anything change if we alter the size of <span class="math-container">$\Sigma$</span> such that <span class="math-container">$|\Sigma|=O(n^k)$</span>? I'm particularly interested in the case where the <span class="math-container">$i^{th}$</span> member of <span class="math-container">$G_n$</span>'s generated output is drawn from a pair. More specifically, we are given <span class="math-container">$n$</span> pairs for each <span class="math-container">$G_n$</span>: <span class="math-container">$T=\{ \{a_1,b_1\},\{a_2,b_2\},\{a_3,b_3\},...\{a_n,b_n\}\}$</span>. Then each output of <span class="math-container">$G_n$</span> is of the form <span class="math-container">$\sigma_1..\sigma_i...\sigma_n$</span> where <span class="math-container">$p_i \in T$</span> and <span class="math-container">$\sigma_i \in p_i$</span>.</li>
<li>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 <span class="math-container">$N_0 \rightarrow \sigma$</span> where <span class="math-container">$\sigma \in \Sigma$</span>, or “hierarchical” categories where they take arguments which are lexical categories. So for example, <span class="math-container">$S \rightarrow N_{01} N_1$</span>, <span class="math-container">$N_1 \rightarrow N_{02} N_2$</span>, <span class="math-container">$N_2 \rightarrow N_{03} N_3$</span>. The cases where <span class="math-container">$N_0 \rightarrow \epsilon$</span> 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.</li>
</ol>
<p>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.</p>

<automata-theory><context-free>
Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?
ShyPerson
# Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?

(Asked by: username_0 on 2021-09-07)

We are given a family of [context-free grammars](https://en.wikipedia.org/wiki/Context-free_grammar) $\{ 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](https://en.wikipedia.org/wiki/Deterministic_finite_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.

**Tags:** automata-theory, context-free


---

## 1 answers

### Answer by username_1 on 2021-09-07. Score: 5 | Accepted answer

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.


---

