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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Dec 9, 2017 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
    Commented Dec 13, 2017 at 12:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.