Autor Tema: Demostrar que no es regular 2

0 Usuarios y 1 Visitante están viendo este tema.

03 Enero, 2020, 04:29 am
Leído 480 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Demuestre que el siguiente lenguaje no es regular.

b) \( L_2=\{a^nb^ma^r, r\ge n\} \).

Hola, podemos usar el Lema de Bombeo?
"Haz de las Matemáticas tu pasión".

04 Enero, 2020, 04:47 am
Respuesta #1

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola, alguien me puede ayudar? Gracias.
"Haz de las Matemáticas tu pasión".

07 Enero, 2020, 03:29 am
Respuesta #2

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola, no lo he podido resolver... ¿Alguien me puede ayudar? Gracias.
"Haz de las Matemáticas tu pasión".

07 Enero, 2020, 04:58 am
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hola, no lo he podido resolver... ¿Alguien me puede ayudar? Gracias.

Todos estos ejercicios son similares. Supón por absurdo que \( L_2 \) es regular, y llama \( n_0 \) a la constante del lema de bombeo. Considera \( w=a^{n_0}ba^{n_0} \).

Spoiler
Esta cadena pertenece a \( L_2 \) y además \( |w|=2n_0+1\geq n_0 \). Por el lema de bombeo, \( w=xyz \) con
  • \( |xy|\leq n_0 \)
  • \( y\ne \epsilon \)
  • \( xy^mz\in L_2,\forall m\in \mathbb{N} \)

Como \( |xy|\leq n_0 \), entonces \( x=a^p,y=a^q \) con \( p+q\leq n_0 \) y \( q>0 \) (lo que es muy importante). Entonces:

\( w=a^pa^qa^{n_0-(p+q)}ba^{n_0},\quad x=a^p,\quad y=a^q,\quad z=a^{n_0-(p+q)}ba^{n_0} \)

Nota ahora que por el punto 3 del lema de bombeo, \( xy^mz\in L_2 \) para todo entero positivo \( m \), es decir, puedes bombear letras \( a \) antes de la \( b \) que las cadenas resultantes seguirán perteneciendo a \( L_2 \). Pero esto es absurdo, porque entonces llegaría un punto que la cantidad de letras \( a \) antes de la \( b \) es mayor que la cantidad de letras \( a \) después de la \( b \), lo que contradice la definición de \( L_2 \).
[cerrar]
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

07 Enero, 2020, 09:13 pm
Respuesta #4

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola, no lo he podido resolver... ¿Alguien me puede ayudar? Gracias.

Todos estos ejercicios son similares. Supón por absurdo que \( L_2 \) es regular, y llama \( n_0 \) a la constante del lema de bombeo. Considera \( w=a^{n_0}ba^{n_0} \).

Spoiler
Esta cadena pertenece a \( L_2 \) y además \( |w|=2n_0+1\geq n_0 \). Por el lema de bombeo, \( w=xyz \) con
  • \( |xy|\leq n_0 \)
  • \( y\ne \epsilon \)
  • \( xy^mz\in L_2,\forall m\in \mathbb{N} \)

Como \( |xy|\leq n_0 \), entonces \( x=a^p,y=a^q \) con \( p+q\leq n_0 \) y \( q>0 \) (lo que es muy importante). Entonces:

\( w=a^pa^qa^{n_0-(p+q)}ba^{n_0},\quad x=a^p,\quad y=a^q,\quad z=a^{n_0-(p+q)}ba^{n_0} \)

Nota ahora que por el punto 3 del lema de bombeo, \( xy^mz\in L_2 \) para todo entero positivo \( m \), es decir, puedes bombear letras \( a \) antes de la primera \( b \) que las cadenas resultantes seguirán perteneciendo a \( L_2 \). Pero esto es absurdo, porque entonces llegaría un punto que la cantidad de letras \( a \) antes de la \( b \) es mayor que la cantidad de letras \( a \) después de la \( b \), lo que contradice la definición de \( L_2 \).
[cerrar]

Muchas Gracias pierrot, me ha quedado claro.  :aplauso:

Saludos.
"Haz de las Matemáticas tu pasión".