Equivalencia de construcciones regulares

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Los lenguajes regulares se pueden generar utilizando variadas construcciones. Todas ellas son equivalentes entre sí como se probará a continuación. La idea es probar que existe una conversión de una construcción en otra.

AFND en AFD[editar]

Para probar que todo AFND puede representarse con un AFD, se construye uno equivalente tomando como estados todos los posibles conjuntos de estados del AFND original (partes de ). Las transiciones entre los estados de este nuevo AFD se definen como las transiciones entre los conjuntos de estados del AFND. Los estados finales del AFD son aquellos conjuntos de estados del AFND que contenían algún estado final. O sea, por ejemplo, si es la función de transición del AFD, .

Una manera de demostrar que ambos aceptan el mismo lenguaje, es demostrar primero que la función de transición extendida mantiene la misma relación que la ya definida partiendo de (el estado inicial), y luego chequear las condiciones de aceptación de una cadena de ambos autómatas.

Para probar que el conjunto de estados al que se llega en el AFND a partir de una cadena x es el estado definido por ese mismo conjunto en el AFD, se hace inducción en la longitud de x para probar . El caso base (longitud cero) es trivial. El paso inductivo parte la cadena x en y + a, siendo a un caracter, y aplica hipótesis inductiva y la definición de delta del AFD.

Al saber que cualquier cadena lleva a estados análogos en el AFND y en el AFD, basta verificar la aceptación de la cadena. En el AFND es aceptada sii en el conjunto de estados al que se llega hay alguno final, mientras que en el AFD cada estado se marca como final si en el conjunto que representa había alguno final. Por lo tanto, el AFND acepta una cadena sii el AFD la acepta, con lo que representan el mismo lenguaje.

AFND-λ en AFND[editar]

Antes de la demostración, es necesario notar que en el caso de los AFND-λ la función de transición extendida para un caracter no es equivalente a la función de transición común (pues la primera efectúa la clausura lambda sobre el conjunto de llegada), con lo cual ya no pueden usarse indistintamente.

La demostración nuevamente es constructiva, a partir de un AFND-λ se crea un AFND que admite el mismo lenguaje. Para esto se toma el mismo conjunto de estados, alfabeto y los mismo estados finales aunque se les agrega el inicial sii tiene algún final en su clausura lambda. La función de transición en el AFND se define como la función de transición extendida (para un caracter) del AFND-λ, es decir, se le agrega la clausura lambda a cada paso.

Intuitivamente, el AFND generado es igual al AFND-λ, pero se quitan las transiciones lambda al agregar transiciones a toda la clausura de la transición original. Por ejemplo, si se tenia y , se reemplaza por y . El único detalle es que para el estado inicial se pierden las transiciones lambda, por eso hay que agregarlo (a veces) a los finales.

El lema intermedio a demostrar en este caso es análogo al anterior: para . Se busca probar por inducción que vale la equivalencia (definida entre las funciones de transición de los autómatas) en la función de transición extendida a partir del estado inicial. Nuevamente se demuestra a partir de separar el primer caracter del resto de la cadena, aplicar la definición original y luego hipótesis inductiva.

Sabiendo que partiendo de los estados iniciales y consumiendo las mismas cadenas en ambos autómatas se llegan a los mismos estados, resta probar que los lenguajes son iguales. Recordar que la condición de aceptación del AFND y del AFND-λ es que la función de transición extendida aplicada a la cadena desde el estado inicial devuelva un conjunto que contenga algún estado final; la diferencia entre AFND y AFND-λ es que la función de este ultimo incluye la clausura lambda a cada paso.

Si la cadena a aceptar es vacía, entonces en el AFNDL la condición de aceptación es que la clausura lambda del estado inicial contenga un final. Como los finales en el AFND equivalente se definieron incluyendo al estado inicial si esto sucedía, entonces lambda es aceptada en uno sii lo es en el otro.

Si la cadena a aceptar es no vacía, entonces ambas funciones de transición llevan al mismo conjunto de estados (por el lema intermedio). Como los estados finales son equivalentes o difieren en , entonces la cadena es aceptada en un autómata sii (hay que separar el análisis según si se agregó a los estados finales o no).

Por lo tanto, el AFND así construido reconoce el mismo lenguaje que el AFNDL original.

Expresiones Regulares en AFND-λ[editar]

Dada cualquier expresion regular, se puede construir un AFND-λ con un unico estado final y sin transiciones a partir de este, haciendo induccion sobre la estructura de la expresion regular.

REtoAFNDL.png

AFD en Expresiones Regulares[editar]

La demostración de la existencia de una expresión regular que captura el mismo lenguaje que un AFD es constructiva. Se basa en la definición de un sublenguaje (o conjunto de cadenas) , previo numerar los estados del autómata de 1 a n.

La expresión representa a todas las cadenas que se obtienen en el automata yendo desde el estado i al estado j pasando por estados de índice a lo sumo k. Notar que i y j pueden ser mayores a k, pero solamente si aparecen como principio y final del camino. Análogamente, se define como la expresión regular cuyo lenguaje es dicho conjunto de cadenas.

La construcción de los R se hace mediante inducción sobre k´y lo que debemos demostrar constructivamente por inducción es que podemos dar una expresión regular cuyo lenguaje es R. El caso base es cuando se tiene , esto es, todos los caminos que van de i a j sin pasar por ningún estado intermedio (pues están numerados a partir de 1). Esto es el conjunto de terminales que se encuentran en todos los arcos que van de i a j, más lambda si i y j son el mismo estado (el conjunto también puede ser vacío). La expresión regular que lo denota es simplemente la disyunción de todos los terminales así obtenidos, con o sin según corresponda, la expresión regular .

Para el paso inductivo, con , para cada camino se pueden dar dos posibilidades. Una es que el camino no pase por ningun estado de índice k, con lo que .

El caso más elaborado es cuando pasa al menos una vez por el nodo k. Cada camino puede partirse entonces en tres partes: desde i a la primera aparición de k, desde la primera aparición de k hasta la ultima (que a su vez se puede dividir como cero o más caminos que empezaron y terminaron en k), y desde la última aparición de k hasta j.

Caminos de i a j pasando una o mas veces por k

Esto puede escribirse como . Sumado al caso en que no se pasa por el nodo k, y reemplazando cada conjunto de cadena por la ER que la representa, se tiene que la expresión regular final que denota las cadenas de es (se aplicó la hipótesis inductiva en cada ).

En castellano, esto significa que para ir del nodo i al j pasando por nodos de a lo sumo índice k, se puede o bien ir directamente de i a j pasando por nodos de a lo sumo k-1, o bien ir hasta k, hacer cero o varios loops, y luego hacer el ultimo tramo de k a j.

Por lo tanto, se pueden generar expresiones regulares para todos los conjuntos de cadenas , esto es, todas las cadenas que resultan de recorrer los caminos de i a j, sin restricción sobre los nodos intermedios.

Notar que el autómata acepta una cadena si existe un camino que la genera que comience en el estado inicial y termine en un estado final. Por lo tanto, las cadenas aceptadas serán aquellas de la forma , con i estado inicial y j algún estado final.

Entonces, la expresión regular que genera el mismo lenguaje que el autómata es , siendo los estados finales del autómata, y 1 el estado inicial.

Gramática regular en AFND[editar]

Dada una gramática regular existe un

Se puede definir como:

La idea es que va a ser un AFND donde cada no terminal sea un estado, los terminales son las etiquetas de las transiciones entre estados y se conecta con por si en está la producción . El estado inicial va a ser el del no terminal distinguido () y se agrega otro estado final () para conectar con si está .

Idea de la demostración:

Se demuestra primero el lema por inducción en :

  • El caso base es aútomático, porque si es vacia, tiene que ser (por las producciones que puede tener la gramática) y por definición de también se cumple lo otro.
  • Luego se prueba para . Se ve que si , de se puede llegar a por por hip. inductiva, y que de se puede llegar a por por la regla 4 de la definición de . Entonces de se puede llegar a por .

Después se debe probar que el lenguaje generado por y es el mismo:

  • Se parte de: .
    • Hay dos formas en que de se puede llegar a la forma sentencial de sólo terminales :
      1. Se llega al final usando como último paso . Entonces, (por el lema aplicado a ), de se llegó a , y (por def. 5) se conecta a por .
      2. La otra opción es que como último paso nos deshacemos de un no terminal que le seguía al terminal , y que desapareció usando . Entonces, por el lema (aplicado a ), de se llega a por , y (por def. 6) es final.
    • Llegamos entonces a que de se llega por a o a un estado final , lo cual es equivalente a .
  • Se ve aparte: .

Lo mismo se puede hacer para una gramatica regular a izquierda, pero cambiando el sentido de las transiciones. Entonces tendriamos que:

AFD en gramática regular[editar]

Dado un AFD existe un gramática regular equivalente. Se demuestra definiendo así y probando luego que y generan el mismo lenguaje.

La idea es casi es la inversa que para pasar de gramática regular a AFND.

Idea de la demostración:

Se demuestra primero el lema por inducción en :

  • El caso base es verdadero por definición en los dos lados del ssi.
  • Se prueba para separando el último paso de y aplicando la hip. inductiva a para llegar a que (donde es el estado anterior para llegar a ) y usando que como de se llega a , por la regla 4 .

Después se debe probar que el lenguaje generado por y es el mismo:

  • Analizamos cadenas no vacias partiendo de . Separamos en el estado al que se llega consumiendo y la última transición por al estado final. Por el lema, al anteúltimo estado se llega con ssi , y por la def. 5 . Esas dos cosas son equivalentes a .
  • Por def. 6 M es final (acepta la cadena vacía) ssi .

Lo mismo se puede hacer con gramática regular a izquierda como en la sección anterior. Con esto se prueba que las gramáticas regulares a izquierda son equivalentes a las a derecha.