Gramática com uma longa derivação gera uma linguagem infinita

Question

.

Deixe $ g $ ser um CFG no formulário normal chomsky que contém $ b $ variáveis.Mostre que se $ g $ gera alguma string com uma derivação com pelo menos $ 2 ^ b $ etapas, então $ l (g) $ é infinito.

Esta questão é de Sipser (introdução à teoria da computação)

Answer 1

Isto segue do lema de bombeamento, se você examinar a prova de perto o suficiente.