0
$\begingroup$

Given a CFG G in Chomsky Normal Form with n variables. Prove that $|L(G)| = \infty \iff \exists w \in L(G)$ such that $2^n<|w|\le2^{n+1}$

Now, proving left to right I've encountered a problem. I am trying to prove it by taking a word above the pumping length, and "pumping down" till I get a word of length in the correct interval. From the pumping lemma for CFL, the substrings we "pump", for example $v,y$ $|vy| \le l=2^n+1$ where $l$ is the pumping length

So when we "pump down" to reach a word within the interval, suppose we reached a word of length $2^{n+1}+1$, and the only appropriate $v,y$ are such that $|vy|=2^n+1$ , we get $2^{n+1}+1 - (2^n+1) = 2^n$ and we "miss" the interval. How is this correct then?

$\endgroup$
  • $\begingroup$ $n$ variables. CNF form has rules of the form A->BC. Look at the proof of the pumping lemma for CFL languages. There are a number of trees involved in the proof. Considering each increase in height corresponds to an extra letter of length in the generated word, and considering the only expansion rule is in the form A->BC, you should be able to argue that you will never get the case that |vy| (in your question's lettering) will never be $2^n+1$ $\endgroup$ – JimN Dec 9 '17 at 23:56
  • $\begingroup$ Do you think this is a correct proof? Falsely assume that $|vy| = 2^n +1$. Corollary from this is that $X=\epsilon$, and from the lemma, $R$ generates $X$ (the smaller subtree that doesn't generate $R$). So that means $R\rightarrow \epsilon$ which cannot be becuase $R$ is not the starting variable and the grammar is in $CNF$ form. contradiction. $\endgroup$ – Eloo Dec 13 '17 at 12:04

Your Answer

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

Browse other questions tagged or ask your own question.