20

Estoy intentando demostrar con el lema del bombeo si la expresion descrita en el titulo es un lenguaje regular o no, esto es lo que he intentado :

∑={a,b}

∃(w)∈L y w = a^i b^j a  , siendo i,j>=0

|w| = 2n+1 >=n , cumple la condicion de |w| >= n

Sabemos que w = xyz con lo cual :

|xy| <= n   ^   1 <= |y| <= n

Siendo X=a^p , y=a^q y que p+q<=n me quedaria al final z=a^(n-p-q) b^n a

De esta forma quedaria |w|= p+q+n-p-q+n+1

comprobando la propiedad de: x y^j z ∈ L para todo j >=0, tenemos que creamos una nueva cadena con j=2 : w' = x y^2 zcon lo cual quedaria :

p + 2q + n - p - q + n + 1 =  2n + 1

Al final se simplifica quedando : q+2n+1 = 2n+1 que solo es cierto si q=0 lo cual no puede ser puesto que la propiedad del propio lema del bombeo dice 1<=|y|<=n

Lo que no entiendo es que si, aplico esto con una cadena, por ejemplo:

w = aaaba

Con n=2 podemos dividir w en :

x=a
y=a
z=aba

Con lo cual para cualquier y^i que se nos ocurra siempre que sea >=0, deberia ser aceptado, pues acaba en a no ??

4
  • 4
    En este sitio se responden preguntas relacionadas con la programación. Tú buscas una explicación formal matemática discreta sobre un tema ligeramente relacionado con la programación. Si sabes de inglés te recomiendo que pruebes suerte en los sitios mathematics o computer science de la red de stack exchange.
    – David DPG
    el 30 jul. 2019 a las 11:41
  • 2
    Es que a primera vista "terminar en a" sí que sería un lenguaje regular, pues puedes generarlo con una gramática regular izquierda de forma bastante trivial. Así que algo hay mal en tu demostración usando el lema de bombeo, pero no lo he examinado con detalle.
    – abulafia
    el 30 jul. 2019 a las 11:50
  • z no es la cadea, de hecho lo es w u w', z es la ultima sucadena, siendo w = xyz, con lo cual las 2 primeras a'es pertenecen una a x y la otra a y
    – k1k4ss0
    el 30 jul. 2019 a las 12:15
  • 4
    Me parece tristísimo que la pregunta tenga (a día de hoy) 4 votos negativos. Podríamos debatir si es o no fuera de ámbito (como se está haciendo en Meta), pero eso se canaliza vía votos de cierre. La descripción emergente del voto negativo dice Esta pregunta no parece tener un trabajo de investigación; es confusa o poco útil. ¿De verdad gente estamos votando negativamente en base a esta descripción?
    – fedorqui
    el 1 ago. 2019 a las 21:11

1 respuesta 1

23

¿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.

5
  • entonces tendria que, si por ejemplo, bombeo 2 veces, en la ecuacion de la derecha agregarle el valor de |y^2|, y en caso de que coincida es que es regular no?, del mismo modo para un numero j de bombeos, agregar el correspondiente |y^j| a la derecha no?, muchas gracias
    – k1k4ss0
    el 30 jul. 2019 a las 15:54
  • No es exactamente como dices @k1k4ss0. El lema de bombeo no puede usarse para demostrar que un lenguaje es regular, sino para demostrar que no lo es. Y la forma sería encontrar una cadena que cumpla con las condiciones del lema (longitud mayor o igual a n, divisible en tres trozos, el primero de ellos de longitud menor o igual a n, el segundo de longitud al menos 1 y el tercero lo que sobre), pero de modo que la cadena xy^jz no forme parte del lenguaje. Ya que según el lema debería serlo, eso demostraría que el lenguaje no es regular.
    – abulafia
    el 30 jul. 2019 a las 16:21
  • En este caso, encontrar una cadena que sí cumpla el lema no demuestra que el lenguaje sea regular, pues para ello deberías demostrar que todas las cadenas cumplen el lema, lo que en general es muy difícil por ser un número infinito de ellas. Por eso el lema se usa para el caso contrario. Basta encontrar una que no lo cumpla para demostrar que el lenguaje no es regular. En este caso naturalmente no vas a poder encontrar ese contraejemplo, porque si que es regular. La forma de demostrar que sí lo es es encontrar una gramática que genere el lenguaje, o una expresión regular que lo detecte.
    – abulafia
    el 30 jul. 2019 a las 16:22
  • muchas gracias ya lo entendi, ademas de que el lema, como dices se tiene que cumplir para cada cadena que sea mayor o igual a n y a su vez que pertenezca al lenguaje, por ejemplo, estube haciendo ejemplos, y si elijo w=a^n, ya no se cumpliria el lema del bombeo, con lo que por mucho que se cumpla el LB con cadenas como w=a^n b^n a, u otro ejemplo, w = b^n a^(n+1), seguiria sin ser un lenguaje no regular pues no cumple con a^n
    – k1k4ss0
    el 30 jul. 2019 a las 20:29
  • Con w=a^n se cumple también.. toma x="" (cadena vacía). y=a^(n-1), y finalmente z=a. Se cumple que |w|=n, y que |xy|<=n, y por tanto ha de cumplirse que xy^jz pertenezca al lenguaje. Y pertenece, ya que sigue terminando en "a". Y es que si no cumpliera para a^n, el lenguaje no sería regular, pero ya hemos encontrado que sí lo es, pues es reconocido por la expresión regular [ab]*a. Si ya sabemos que es regular, sabemos también que el LB se va a cumplir para todas sus cadenas. No hay que darle más vueltas al LB. No vas a encontrar un contraejemplo porque no lo hay, pues es regular
    – abulafia
    el 30 jul. 2019 a las 20:47

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.