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?
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?
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 -state DFA es infinito si y solo si acepta alguna palabra cuya longitud se encuentra entre y .
El lema de bombeo implica la dirección.
También "da otra prueba" de que el lenguaje no es regular (la prueba original en el documento usa la teoría de Myhill-Nerode).