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 w
- El | | ≥ 1
- El | | ≤p
- para todo ≥ 0, ∈x y i z L
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 b
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 y
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 b
Obviamente me estoy perdiendo algo increíblemente obvio. ¿Cual es?
fuente
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.L L
Según wikipedia ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), el lema de bombeo dice:(∀L⊆Σ∗)(regular(L)⇒((∃p≥1)((∀w∈L)((|w|≥p)⇒((∃x,y,z∈Σ∗)(w=xyz∧(|y|≥1∧|xy|≤p∧(∀i≥0)(xyiz∈L))))))))
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 .L lmax L p lmax+1 L ≥lmax+1
fuente
Una forma de formalizar la parte central del lema de bombeo es esta, utilizando :L≥k={w∈L∣|w|≥k}
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 .L p>max{|w|∣w∈L} L≥p=∅ p
fuente