¿Para qué es el lema de bombeo?

8

Esto es algo que no pude encontrar, pero siempre me pareció interesante que el lema de bombeo sea solo un lema (especialmente porque tiene el mismo nombre para idiomas normales, idiomas libres de contexto, etc.)

¿Para qué es un lema?

Aria
fuente

Respuestas:

9

En el documento fundacional de Rabin y Scott, autómatas finitos y sus problemas de decisión , el lema de bombeo aparece como un lema (Lema 8) con el siguiente resultado (Teorema 9):

El idioma aceptado por un norte-state DFA es infinito si y solo si acepta alguna palabra cuya longitud se encuentra entre norte y 2norte.

El lema de bombeo implica la dirección.

También "da otra prueba" de que el lenguaje {0 0norte10 0norte:norte0 0} no es regular (la prueba original en el documento usa la teoría de Myhill-Nerode).

Yuval Filmus
fuente