Suppose $G$ is a CNF (Chomsky normal form ) grammar which has $v$ variables. ($|V| = v$) If there is a string that $G$ derivatives in more than $2^v$ steps, prove that $L(G)$ is infinite.
Any ideas how can i prove this?
I know derivation tree in a CNF grammar is binary. So my idea is to calculate maximum number of leaves in the tree and prove that if $L(G)$ is finite this can't be reached in more than $2^v$ steps. Can anyone help me how to prove this part?
G is in CNF. We can ignore the derivation S->eps since it is the only derivation of an empty string so it is only part of a derivation of length 1. I assume that the start symbol S counts as one of the "variables" or non-terminals, so there are (v-1) other non-terminals. S can only appear at level zero of the derivation.
In a derivation, every step replaces a non-terminal with a terminal, or increases the number of non-terminals by 1. Therefore, if N generates a string x of terminals and non-terminals, x is either a single terminal with a one-step derivation, or x consists of at least two symbols.
If G generates a string s, and in the derivation a symbol N derives itself (N -> x N y, where x, y are strings of terminal and non-terminal symbols), then we found that either x or y are non-empty, and derive non-empty strings of terminals (since they were part of a derivation). And since we derived N -> x N y, we can derive N -> $x^k N y^k$ for any k > 0, so the language is infinite.
So we have seen that if a non-terminal N occurs twice in any derivation, the language is infinite. Now look at the derivation of a tree. Level k of the tree has at most $2^k$ nodes. If the tree has a height h, then the nodes at levels $k = 0$ to $k = h-1$ may have contributed a derivation step, for a total of $2^h-1$ derivation steps. If a string s is derived in more than $2^v$ steps (actually, in $2^v$ or more steps), then it has a height v+1 or greater. If you look at a node at level v+1, then there are v non-terminals at levels 1 to v, and since there are only v-1 non-terminals after than S, one non-terminal must occur twice. Which makes the language infinite.
We can make any grammar epsilon-free quite easily: Introduce a new symbol $S_0$ and a rule $S_0->S$, so that $S_0$ will not occur on any right hand side of a rule. Then as long as there is a derivation N->eps with N ≠ $S_0$, remove that derivation, and for every rule with N on the right hand side, add rules with any possible subset of these N's removed. Remove all duplicate rules, and the only rule containing eps that is possibly left is $S_0 -> eps$. In an epsilon-free grammar we have the same fact that if the grammar contains a string s where the derivation contains a derivation N -> x N y where x or y are non-empty, then the language is infinite.
Here is the proof of the analogous result for regular languages. Hopefully you can generalize it to your case.
Theorem. Suppose that $A$ is a DFA on $n$ states such that $L(A)$ contains a word of length at least $n$. Then $L(A)$ is infinite.
Proof. Let $w = w_1 \ldots w_N \in L(A)$ be a word of length $N \geq n$, and let $q_i = \delta(q_0,w_1\ldots w_i)$ for $0 \leq i \leq N$. Since $N \geq n$, the sequence $q_0,\ldots,q_N$ contains $N+1 > n$ elements, and so $q_i = q_j$ for some $i < j$. Let $x = w_1 \ldots w_i$, $y = w_{i+1} \ldots w_j$, $z = w_{j+1} \ldots w_N$. We have $$ q_j = \delta(q_0,xy) = \delta(\delta(q_0,x),y) = \delta(q_i,y). $$ Since $\delta(q_i,y) = q_i$, an easy induction shows that $\delta(q_i,y^t) = q_i$ for all $t \geq 0$, and so $$ \delta(q_0,xy^tz) = \delta(\delta(\delta(q_0,x),y^t),z) = \delta(\delta(q_i,y^t),z) = \delta(q_i,z) = \\ \delta(q_j,z) = \delta(\delta(q_0,xy),z) = \delta(q_0,xyz) \in F, $$ where $F$ is the set of accepting states. This shows that $xy^tz \in L(A)$ for all $t \geq 0$. Since $y \neq \emptyset$, it follows that $L(A)$ is infinite. $\square$
Note the similarity to the proof of the pumping lemma. A similar idea works in your case, in which one of the nonterminals will repeat twice.
