¿Es regular?

Hice mi examen de teoría de la computación hace unas semanas, y esta fue una de las preguntas:

Asumir lenguaje $L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$

¿L es regular? En caso afirmativo, proporcione una expresión regular o un autómata para ello.

Después de preguntarle brevemente la respuesta después del examen, parece que realmente es regular (creo que dijo que la expresión es simple ). Sin embargo, parece que no puedo entender por qué es así. A mi modo de ver, se concatena r veces, así: $(a^*b^*)^*$ $a^nb^m$

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$ ,

lo cual no es regular ya que no hay forma de que un autómata recupere n y m cada vez. ¿Dónde tengo la culpa aquí?

EDITAR: volví a hablar con el profesor, admitió que fue un error. El lenguaje de hecho no es regular.

formal-languages regular-languages regular-expressions Exci
fuente

Debería preguntarle a su maestro si el idioma es el mismo que el idioma . Si dice "sí", dígale que le dije que su pregunta estaba mal formada.

L

$L$

K = {a^{n_{1}} b^{m_{1}} a^{n_{2}} b^{m_{2}} \dots a^{n_{r}} b^{n_{r}} ∣ r \geq 0, a_{1}, \dots, a_{r} \geq 0, b_{1}, \dots, b_{r} \geq 0}

$K = \lbrace a^{n_1} b^{m_1} a^{n_2} b^{m_2} \cdots a^{n_r} b^{n_r} \mid r \geq 0, a_1, \ldots, a_r \geq 0, b_1, \ldots, b_r \geq 0\rbrace$

Andrej Bauer

Esa parece ser la única forma en que podría ser regular, y de hecho esto es lo que originalmente pensé apresuradamente y realmente consideré (a b ) *, pero luego lo borré al darme cuenta de que nym permanecen igual (o deberían ...), y di una desaprobación de lema de bombeo para r = 2, diciendo que lo mismo se aplicó para r más grande (probablemente tampoco sea una solución completa pero parece estar en la dirección correcta). No hace falta decir que obtuve 0 para esa pregunta. Intentaré contactarlo.

Ciertamente entendería la pregunta de la manera que lo hizo inicialmente.

Andrej Bauer

Vea aquí más formas de mostrar que un idioma no es regular.

Raphael

también podría probar lo mismo con la ayuda de bombear lema

SAHIL THUKRAL

Respuestas:

El lenguaje no es regular, como se puede probar usando el método de Nerode. Considere las siguientes palabras para . Entonces , pero para , . Por lo tanto, cualquier autómata para debe estar en un estado diferente después de leer cada , lo que contradice su finitud. $L$ $w_n = a^n b$ $n \in \mathbb{N}$ $w_n^2 \in L$ $n \neq m$ $w_n w_m \notin L$ $L$ $w_n$

Yuval Filmus
fuente

En su comentario, insinúa que (cita) "dio una desaprobación de lema de bombeo para , diciendo que lo mismo se aplica para más grande ". $r=2$ $r$

De hecho, esto puede formalizarse aplicando una propiedad de cierre. Los idiomas regulares están cerrados bajo intersección. Así que si es regular, entonces también lo sería , estableciendo efectivamente y . $L$ $L\cap a^*ba^*b = \{ a^n b a^n b \mid n\ge 0\}$ $r=2$ $m=1$

Hendrik Jan
fuente

Estimado lector, por favor no quite "si no es regular, entonces tampoco lo es ", ¡porque eso es falso!

L

$L$

L^{'} \supset L

$L' \supset L$

Raphael

@Raphael Right. Entonces, la implicación correcta sería "si no es regular, entonces tampoco lo es ", donde es regular.

L \cap R

$L\cap R$

L

$L$

R

$R$

Hendrik Jan

Por supuesto. Me preocupaba que los principiantes pudieran leer "configuración efectiva ..." y aplicar esto sin usar las propiedades de cierre.

Raphael

El lenguaje: {(a ⁿ b ^m ) ^r | n, m, r≥0} no es regular, porque mientras el autómata / máquina lee la primera secuencia de letras 'a' y luego las letras 'b', necesita contar el número de veces que lee la letra 'a' y el número de veces que leer la letra 'b' en la primera secuencia para conocer el valor de n y m .

Si r> 1 luego otro mismo se espera secuencia de letras 'a' y las letras 'B'.

Si el autómata / máquina no no sabe cuántas letras 'a' y letras 'b' se lee en la primera secuencia, entonces tampoco no sabe el valor de n y m , y por lo tanto puede no saber si las otras secuencias del penúltimo son palabras que son iguales a la primera secuencia.

Sin embargo, se sabe que la única máquina de Turing puede contar y conocer los valores de n y m y reconocer el lenguaje anterior, por lo que no sólo que el lenguaje anterior es no regular, pero incluso también es no libre de contexto, es decir, también lo hace No existe un autómata pushdown para reconocer este idioma y no existe una gramática libre de contexto que cada palabra derivada de esa gramática libre de contexto esté en el idioma anterior.

Debido a que el hecho de que tanto determinista finita autómata de pila finita autómata puede no contar y conocer los valores de n y m , a diferencia de la máquina de Turing, que pueden no reconocer el idioma arriba y por lo tanto el lenguaje anterior es no libre de contexto y no es regular

Contraejemplo a la suposición de que el lenguaje anterior es regular:

Para n = 3 ∧ m = 5 ∧ r = 2 , la siguiente palabra está en el idioma anterior:

aaabbbbbaaabbbbb

Pero la siguiente palabra no está en el idioma:

aaabbbbbaaaaabbb, porque no no existir n, m y r so:

(a ⁿ b ^m ) ^r = aaabbbbbaaaaabbb, porque para satisfacer la primera secuencia de letras 'a' y luego las letras 'b', debe ser cierto que n = 3 ∧ m = 5 , y porque vemos 2 secuencias de letras ' a 'y luego letras' b ', entonces r = 2 , pero si n = 3 ∧ m = 5 ∧ r = 2 entonces (a ⁿ b ^m ) ^r = (a ³ b ⁵ ) ² = (aaabbbbb) ² = aaabbbbbaaabbbbb ≠ aaabbbbbaaaaabbb, porque sus sufijos son diferentes, es decir, aaabbbbb ≠ aaaaabbb, aunque sus prefijos son iguales a aaabbbbb para r = 1.

El "mejor" autómata finito determinista que se puede construir para este lenguaje es el autómata finito determinista que reconoce la expresión regular (a * b *) *, pero no reconoce el lenguaje anterior, porque dice que ambas palabras aaabbbbbaaabbbbb y aaabbbbbaaaaabbb están en el idioma y esto no es cierto, porque aaabbbbbaaabbbbb está en el idioma, pero aaabbbbbaaaaabbb no está en el idioma.

Incluso el autómata finito pushdown no puede decir si ambas palabras están en el idioma o no, por lo que solo la máquina Turing puede.

En la segunda secuencia, la máquina de Turing encontró que n = 5 ∧ m = 3 y esto contradice que en la primera secuencia encontró que n = 3 ∧ m = 5 , por lo que dice que la segunda palabra no está en el idioma , pero no se encuentra contradicción en la primera palabra.

Ambas secuencias satisfacen que n = 3 ∧ m = 5 , por lo que la máquina de Turing dice que la primera palabra está en el idioma.

Sólo Turing máquina puede, si cuenta y recuerda los valores de n y m escribiendo su valor sobre el mismo de la cinta y luego leerlos.

Despedida de cambio de pila
fuente