1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Hint: check out the proof of the pumping lemma. $\endgroup$ – Raphael Nov 19 '17 at 11:29
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.