Lema de bombeo para idiomas regulares finitos simples

20

Wikipedia tiene la siguiente definición del lema de bombeo para idiomas regulares ...

Deje que sea ​​un lenguaje regular. Entonces existe un número entero ≥ 1 que depende solo de modo que cada cadena en de longitud al menos ( se llama "longitud de bombeo") se puede escribir como = (es decir, se puede dividir en tres subcadenas), que cumplan las siguientes condiciones:p L w L p p w x y z wLpLwLppwxyzw

  1. El | | ≥ 1y
  2. El | | ≤pxyp
  3. para todo ≥ 0, ∈x y i z LixyizL

No veo cómo esto se satisface para un lenguaje regular finito simple. Si tengo un alfabeto de { } y la expresión regular entonces consta de sólo una palabra que se seguida por . Ahora quiero ver si mi lenguaje normal satisface el lema de bombeo ...a b L a ba,babLab

Como nada se repite en mi expresión regular, el valor de debe estar vacío para que la condición 3 se satisfaga para todo . ¡Pero si es así, falla la condición 1 que dice que debe tener al menos 1 de longitud!i yyiy

Si, en cambio, dejo que sea , o , satisfará la condición 1 pero fallará la condición 3 porque en realidad nunca se repite.a b a byabab

Obviamente me estoy perdiendo algo increíblemente obvio. ¿Cual es?

Phil Wright
fuente

Respuestas:

29

Tienes razón: no podemos permitir palabras de "bombeo" de una finita . Lo que falta es que el lema dice que existe un número p , pero no nos dice el número.Lp

Todas las palabras más largas que pueden ser bombeadas, por el lema. Para una finita L , sucede de manera que p es mayor que la longitud de la palabra más larga en L . Por lo tanto, el lema solo se mantiene vacío, y no se puede aplicar a ninguna palabra en L , es decir, cualquier palabra en L no cumple la condición de "tener una longitud de al menos p " como lo requiere el lema.pLpLLLp


Un corolario: si tiene una longitud de bombeo p , y existe alguna palabra w L de longitud al menos p , entonces L es infinito.LpwLpL

Sonó.
fuente
2
Un buen ejemplo del conjunto vacío cumplimiento -statements.
Raphael
7

El lema de bombeo generalmente se usa en idiomas infinitos, es decir, idiomas que contienen un número infinito de palabras. Para cualquier lenguaje finito , dado que siempre puede ser aceptado por un DFA con un número finito de estado, L debe ser regular.LL

Según wikipedia ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), el lema de bombeo dice: (LΣ)(regular(L)((p1)((wL)((|w|p)((x,y,zΣ)(w=xyz(|y|1|xy|p(i0)(xyizL))))))))

Para cualquier lenguaje finito , dejemos que l m a x sea ​​la longitud máxima de las palabras en L , y dejemos que p en el lema de bombeo sea l m a x + 1 . El lema de bombeo se mantiene ya que no hay palabras en L cuya longitud l m a x + 1 .LlmaxLplmax+1Llmax+1

Wu Yin
fuente
2

Una forma de formalizar la parte central del lema de bombeo es esta, utilizando :Lk={wL|w|k}

Si es regular, existe p N para queLpN

(*).wLp. x,y,z

Para todos finita y P > max { | w | w L } , obviamente tenemos que L p = . Por lo tanto (*) es (al vacío) verdadero para tal p .Lp>max{|w|wL}Lp=p

Rafael
fuente