¿Qué es un lenguaje regular?
Un lenguaje que pueda ser generado a partir de una gramática regular, o que pueda ser reconocido por una expresión regular.
¿Qué es una gramática regular?
Es un conjunto formado por:
- Un alfabeto (representado por ∑) que no es más que un conjunto de símbolos, en este caso los símbolos "a" y "b". Estos son simbolos terminales porque una vez se ha usado uno de ellos, ya no se "expande" para generar otros. Se considera también un signo terminal a ε, que representa la cadena vacía.
- Un conjunto de "símbolos no terminales" (denotado por N) que son símbolos que usaremos para representar "sub-cadenas" del lenguaje, por así decir, aún sin terminar, mientras las estamos generando.
- Un conjunto de reglas (denotado por P) que dice cómo cada símbolo no terminal se puede convertir en otros (terminales o no terminales). Las definiciones pueden ser recursivas, un simbolo no terminal pude generar una expansión que se contenga a sí mismo.
- Un simbolo no-terminal por el que se empieza la producción.
¿Es tu caso un lenguaje regular?
Sí, porque puede ser generado por la siguiente gramática regular:
- Vocabulario ∑={a,b}
- Símbolos no-terminales N={S, A}. El símbolo S representa el de inicio.
- Conjunto de reglas P como sigue:
- S -> Aa
- A -> aA
- A -> bA
- A -> ε
Empezando por S, la regla me dice que puedo expandirlo como "el símbolo no-temrinal A", seguida del carácter "a". El símbolo no-terminal "A" a su vez se puede expandir bien como la cadena vacía, bien como una letra "a" seguida otra vez del símbolo A (que puede volver a expandirse por cualquiera de sus reglas, y así sucesivamente) o bien como una letra "b" seguida otra vez del símbolo A (que de nuevo puede volver a expandirse, etc)
Esta gramática genera cadenas como "a", "aa", "ba", "abbaabbababa", etc. Este lenguaje sería reconocido por la expresión regular [ab]*a
.
Debido a la primera regla de P
, todas las cadenas del lenguaje siempre van a terminar en a.
¿Entonces el lema del bombeo?
El lema del bombeo dice que si un lenguaje es regular, entonces ha de existir una longitud mínima n
tal que cualquier cadena que tenga esa longitud, tiene una "parte central" por así decir, que se puede repetir cuantas veces se quiera, y el resultado seguirá siendo parte del lenguaje regular.
En este caso la longitud mínima es 2. Cualquier cadena de longitud 2 o mayor en este lenguaje termina por "a", y puede escribirse en la forma xyz, siendo x=ε (cadena vacía),y
=todas las letras salvo la "a" final, y finalmente z=a
(la "a" final). Repitiendo y
cuantas veces queramos: xy^jz
va a seguir saliendo una cadena terminada en "a", que será parte del lenguaje.
El lema del bombeo suele usarse para demostrar que un lenguaje no es regular, buscando una cadena que no pueda descomponerse de este modo. Ya que en este caso tenemos un lenguaje regular, el lema del bombeo no es de utilidad, no podremos encontrar ese contraejemplo.
Tu error creo que estuvo en la igualdad:
p + 2q + n - p - q + n + 1 = 2n + 1
En ella estás intentando hacer iguales las longitudes de las cadenas después del bombeo (es decir, después de repetir la parte y
2 veces) y antes del bombeo, cuando la y
aparecía una sola vez.
Naturalmente es imposible que ambas longitudes coincidan, a menos que bombees cero veces o que la longitud de y
sea cero. No hay por qué suponer que esas longitudes sean iguales. De hecho, ningún lenguaje regular lo cumpliría.