-2
$\begingroup$

Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$ generates some string with a derivation having at least $2^b$ steps, then $L(G)$ is infinite.

This question is from Sipser(Introduction to the theory of computation)

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you made any attempts to solve this question? $\endgroup$
    – Yuval Filmus
    Commented May 23, 2020 at 13:40
  • $\begingroup$ Where did you encounter this question? Please credit the source of all copied material. $\endgroup$
    – D.W. ♦
    Commented May 23, 2020 at 23:21

1 Answer 1

Reset to default
4
$\begingroup$

This follows from the pumping lemma, if you examine the proof closely enough.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thx for the tip. So here are my thoughts. Since we have b variables, the height of the parsing tree can be maximum b +1, therefore for a word which is at least of length $2^b$ there must be a repeated nonterminal on this branch which I can pump up $\endgroup$
    – Frank
    Commented May 23, 2020 at 14:11
  • $\begingroup$ Right, that's the idea. $\endgroup$
    – Yuval Filmus
    Commented May 23, 2020 at 14:14

Your Answer

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

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