Demostraciones (Teoría de Lenguajes)

Lenguajes Regulares

Autómatas

Función de transición extendida

La función de transición extendida o generalizada se define recursivamente sobre la cadena a la que se aplica. En el caso base (cadena vacía) devuelve el mismo estado (o su clausura lambda en un AFND-λ); en el inductivo, toma la cadena w + a y devuelve el conjunto resultante de aplicar la transición por a al conjunto de estados generado por la transicion sobre w.

• Caso Base: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat \delta (q, \lambda) = q}
• Caso Recursivo: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat \delta (q, wa) = \delta(\hat \delta (q, w), a)}

Esta naturaleza recursiva permite demostrar propiedades sobre la función de transición generalizada a partir de propiedades de la función de transición común utilizando inducción sobre la longitud de la cadena. Supongamos se tiene una función Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta} igual a una Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta \prime} , se quiere probar que la igualdad vale tambien para la generalizada:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat \delta \prime (q_0, wa) = \delta \prime (\hat \delta \prime (q_0, w), a)} por definición de generalizada,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle = \delta \prime (\hat \delta (q_0, w), a) } por HI,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle = \delta (\hat \delta (q_0, w), a)} por igualdad entre delta,
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle = \hat \delta (q_0, wa)} por definicion de generalizada.

Este esquema puede usarse para probar equivalencias o propiedades sobre funciones generalizadas dadas las de las funciones no generalizadas, y eventualmente predicar sobre el lenguaje en lugar de solamente caracteres.

Lenguaje aceptado por un automata

El lenguaje aceptado por un autómata generalmente se define como el conjunto de cadenas que derivan en un estado final al consumirse partiendo del estado inicial. Es decir, se define en función de la funcion de transicion extendida.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle w \in L(M) \Leftrightarrow \exists q_f \in \hat \delta (q_0, w)}

Esto hace que demostrar una propiedad sobre la función de transición extendida permita demostrar propiedades sobre el lenguaje aceptado por un autómata. Al demostrar equivalencia entre autómatas, conviene demostrar equivalencias entre funciones de transición extendidas.

Equivalencias

AFND en AFD

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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Q} ). 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta'} es la función de transición del AFD, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta'([q_1,...,q_j], a) = [p_1,...,p_i] \Leftrightarrow \delta(\{q_1,...,q_j\},a) = \{p_1,...,p_i\}} .

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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_0} (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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta'([q_0], x) = [p_1,...,p_i] \Leftrightarrow \delta(q_0,x) = \{p_1,...,p_i\}} . 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-L en AFND

Antes de la demostración, es necesario notar que en el caso de los AFND-L 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-L 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-L, es decir, se le agrega la clausura lambda a cada paso.

Intuitivamente, el AFND generado es igual al AFND-L, pero se quitan las transiciones lambda al agregar transiciones a toda la clausura de la transición original. Por ejemplo, si se tenia Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow aB} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle B \rightarrow \lambda C} , se reemplaza por Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow aB} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle A \rightarrow aC} . 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: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \delta'(q_0, x) = \delta\hat (q_0, x)} para Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |x| \ge 1} . 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-L 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-L 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_0} , 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_0} o no).

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

Expresiones Regulares en AFND-L

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

AFD en Expresiones Regulares

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) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R^k_{i,j}} , previo numerar los estados del autómata de 1 a n.

La expresión Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R^k_{i,j}} 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle r^k_{i,j}} 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R^0_{i,j}} , 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda} según corresponda, la expresión regular Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \emptyset} .

Para el paso inductivo, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R^k_{i,j}} con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k \geq 1} , para cada camino se pueden dar dos posibilidades. Una es que el camino no pase por ningun estado de índice k, con lo que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle r^k_{i,j} = r^{k-1}_{i,j}} .

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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R^{k-1}_{i,k} (R^{k-1}_{k,k})^* R^{k-1}_{k,j}} . 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R_{i,j}^k} es Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle r^{k-1}_{i,j} | r^{k-1}_{i,k} (r^{k-1}_{k,k})^* r^{k-1}_{k,j}} (se aplicó la hipótesis inductiva en cada Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R^{k-1}} ).

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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R^n_{i,j}} , 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle R^n_{i,j}} , 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle r^n_{1,f_1} | r^n_{1,f_2} | \ldots | r^n_{1,f_m}} , siendo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_1 \ldots f_m} los estados finales del autómata, y 1 el estado inicial.

Gramaticas Regulares en AFND

Dada una gramática regular Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G = \langle V_n, V_T, P, S\rangle} existe un Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle AFND} Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle M = \langle Q, \Sigma, \delta, q_0, F \rangle}

Se puede definir Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle M} como:

1. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Q = V_N \cup \{q_f\}}
2. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Sigma = V_T}
3. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_0 = q_s}
4. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_B \in \delta(q_A, a) \leftrightarrow A \rightarrow aB \in P}
5. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_f \in \delta(q_A, a) \leftrightarrow A \rightarrow a \in P}
6. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_A \in F \leftrightarrow A \rightarrow \lambda \in P}
7. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q_f \in F}

La idea es que $M$ va a ser un AFND donde cada no terminal sea un estado, los terminales son las etiquetas de las transiciones entre estados y $q_{A}$ se conecta con $q_{B}$ por $a$ si en $G$ está la producción $A\rightarrow aB$. El estado inicial va a ser el del no terminal distinguido ($q_{S}$) y se agrega otro estado final ($q_{f}$) para conectar con $q_{A}$ si está $A\rightarrow a$.

Idea de la demostración:

Se demuestra primero el lema $A\Rightarrow ^{*}wB\Leftrightarrow q_{B}\in \delta (q_{A},w)$ por inducción en $w$:

• El caso base $w=\lambda$ es aútomático, porque si $w$ es vacia, $B$ tiene que ser $A$ (por las producciones que puede tener la gramática) y por definición de $\delta$ también se cumple lo otro.
• Luego se prueba para $w=\alpha a$. Se ve que si $A\Rightarrow ^{*}\alpha C$ y $C\rightarrow aB$, de $q_{A}$ se puede llegar a $q_{C}$ por $\alpha$ por hip. inductiva, y que de $q_{C}$ se puede llegar a $q_{B}$ por $a$ por la regla 4 de la definición de $M$. Entonces de $q_{A}$ se puede llegar a $q_{B}$ por $\alpha a$. Para probarlo para el otro lado, se ve que si se puede llegar a $q_{B}$ por $\alpha a$, entonces se puede llegar a un estado $q_{C}$ por $\alpha$ que llega a $q_{B}$ por $a$. Como sólo agregamos una transición a un estado $q_{B}$ si existe $C\rightarrow aB$, esta producción existe en G. Por hipótesis inductiva, $A\Rightarrow ^{*}\alpha C$. Por lo tanto, $A\Rightarrow ^{*}\alpha C\Rightarrow \alpha aB$, o sea, $A\Rightarrow ^{*}\alpha aB$.

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

• Se parte de: $wa\in L(G)\Leftrightarrow S\Rightarrow ^{*}wa$ .
  • Hay dos formas en que de $S$ se puede llegar a la forma sentencial de sólo terminales $wa$:
    1. Se llega al $a$ final usando como último paso $A\rightarrow a$. Entonces, (por el lema aplicado a $w$), de $q_{S}$ se llegó a $q_{A}$, y (por def. 5) $q_{A}$ se conecta a $q_{f}$ por $a$.
    2. La otra opción es que como último paso nos deshacemos de un no terminal $B$ que le seguía al terminal $a$, y que desapareció usando $B\rightarrow \lambda$. Entonces, por el lema (aplicado a $waB$), de $q_{S}$ se llega a $q_{B}$ por $wa$, y (por def. 6) $q_{B}$ es final.
  • Llegamos entonces a que de $q_{S}$ se llega por $wa$ a $q_{f}$ o a un estado final $q_{B}$, lo cual es equivalente a $wa\in L(M)$.
• Se ve aparte: $\lambda \in L(G)\;\Leftrightarrow \;S\rightarrow \lambda \;\Leftrightarrow \;q_{S}\in F\;\Leftrightarrow \;\lambda \in L(M)$.

AFD en Gramáticas Regulares

Dado un AFD $M=<Q,\Sigma ,\delta ,q_{0},F>$ existe un gramática regular $G=<V_{n},V_{T},P,S>$ equivalente. Se demuestra definiendo $G$ así y probando luego que $M$ y $G$ generan el mismo lenguaje.

1. $V_{N}=Q$
2. $V_{T}=\Sigma$
3. $S=A_{q_{0}}$
4. $A_{p}\rightarrow aA_{q}\in P\leftrightarrow q=\delta (p,a)$
5. $A_{p}\rightarrow a\in P\leftrightarrow \delta (p,a)\in F$
6. $S\rightarrow \lambda \in P\leftrightarrow q_{0}\in F$

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 $\delta (p,w)=q\Leftrightarrow A_{p}\Rightarrow ^{*}wA_{q}$ por inducción en $w$:

• El caso base $w=\lambda$ es verdadero por definición en los dos lados del ssi.
• Se prueba para $w=\alpha a$ separando el último paso de $\delta$ y aplicando la hip. inductiva a $\alpha$ para llegar a que $A_{p}\Rightarrow ^{*}wA_{x}$ (donde $x$ es el estado anterior para llegar a $q$) y usando que como de $x$ se llega a $q$, por la regla 4 $A_{x}\rightarrow aA_{q}$.

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

• Analizamos cadenas no vacias partiendo de $wa\in L(M)\Leftrightarrow \delta (q_{0},wa)\in F$ . Separamos $\delta$ en el estado $p$ al que se llega consumiendo $w$ y la última transición por $a$ al estado final. Por el lema, al anteúltimo estado $p$ se llega con $w$ ssi $A_{q_{0}}\Rightarrow ^{*}wA_{p}$, y por la def. 5 $A_{p}\rightarrow a$. Esas dos cosas son equivalentes a $A_{q_{0}}\Rightarrow ^{*}wa$.
• Por def. 6 $q_{0}$ M es final (acepta la cadena vacía) ssi $S\rightarrow \lambda$.

Propiedades

Unión

El conjunto de lenguajes regulares incluido en $\Sigma ^{*}$ es cerrado respecto de la unión. Dados $L_{1}$ = $L(M_{1})$ y $L_{2}=L(M_{2})$, $L_{1}\cup L2$ es un lenguaje regular.

• Esto es inmediato con expresiones regulares, ya que el lenguaje generado por $ER(L_{1})+ER(L_{2})$ es regular y el más es por definición la unión de los lenguajes $L_{1}$ y $L_{2}$.

• Si lo queremos probar con autómatas, basta con: pegar $M_{1}$ al lado de $M_{2}$, agregar un estado inicial $q_{0}$ que tiene transiciones a los mismos estados (y por los mismos símbolos) que los iniciales de $M_{1}$ y $M_{2}$, marcarlo como final si alguno de los lenguajes acepta la cadena vacía y listo (transiciones y finales queda igual).

Complemento

El complmento de un lenguaje regular es regular

• Una forma constructiva de probar esto es tomando el AFD del lenguaje y complementando el conjunto de estados finales (poniendo los finales como no finales y vicevera). Es inmediato que esto genera el complemento. Si $\Delta$ es el alfabeto del autómata y queremos tomar el complemento respecto a un superconjunto $\Sigma$ de $\Delta$, basta con encontrar el autómata del complemento $M'$ y calcular: $L(M')\cup \Sigma ^{*}(\Sigma -\Delta )\Sigma ^{*}$ (notar que es una unión de lenguajes regulares). Recordar que el AFD debe estar completo (tener el estado "trampa").

Intersección

La intersección de un lenguaje regular es regular

Es inmediata usando la ley de DeMorgan, ya que $L_{1}\cap L_{2}={\overline {{\overline {L_{1}}}\cup {\overline {L_{2}}}}}$.

También se puede realizar de forma constructiva a partir de los autómatas. Se arma un gran autómata que tiene como estados el producto cartesiano de los estados de los otros dos de forma tal que un estado $(a,b)$ es final si $a$ y $b$ son finales en sus respectivos autómatas.

Unión e Intersección finita

La unión finita y la intersección finita de lenguajes regulares dan por resultado un leguaje regular. Es trivial de probar con una inducción.

Esto NO VALE para INFINITO. (pensar en la unión infinita de $a^{k}b^{k}$)

Pertenencia

Saber si una cadena pertenece a un lenguaje regular es decidible (Dado el lenguaje regular, se construye su AFD y se pone a prueba la cadena).

Finitud

Todo lenguaje finito es regular. Ya que se puede ver como la unión finita de los elementos uno a uno.

Determinar si un lenguaje regular es finito es decidible

Un lenguaje regular es finito si en su AFD ningún estado desde el cual se pueda alcanzar un estado final puede dar lugar a un "ciclo".

Alternativamente, un lenguaje regular es infinito sii su AFD acepta al menos una cadena de longitud $k$ tal que $2n>k\geq n$, donde $n$ es la cantidad de estados del AFD.

Vacuidad

Determinar si un lenguaje regular es vacío es decidible. Se construye el AFD y se mira si alguno de los estados alcanzables es final.

Equivalencia

Determinar si dos lenguajes regulares son equivalentes es decidible. Se construyen sus respectivos autómatas. Luego se construye el autómata de $(L_{1}\cap {\overline {L_{2}}})\cup ({\overline {L_{1}}}\cap L_{2})$. Si es vacío, son equivalentes, sino no lo son.

Lema de Pumping

Transición para Config Instantánea

La función de transición entre dos configuraciones instantáneas se define como $(q,a\alpha )\vdash (p,\alpha )$ sii existe una transición de q a p por a. Asimismo se define la función de transición generalizada.

Vale que si $(q,\alpha \beta )\vdash ^{*}(q,\beta )$, entonces $(q,\alpha ^{i}\beta )\vdash ^{*}(q,\beta )$ para cualquier $i\geq 0$. Es decir, si es posible hacer un loop sobre el estado q consumiendo la cadena alfa, entonces es posible realizar ese loop tantas veces como se desee. Se demuestra fácilmente por inducción en la cantidad de repeticiones de alfa.

Pumping

El lema de pumping expresa que dada una longitud mínima n (que depende del lenguaje), todas las cadenas z de longitud mayor o igual a n pueden escribirse como z = uvw, donde uv no supera a n, v es no vacía y es posible repetir tantas veces v como se desee sin que la cadena deje de pertenecer al lenguaje. Es decir, $uv^{*}w$ pertenece al lenguaje.

Intuitivamente, significa que existe una longitud n (para la cual puede tomarse la cantidad de estados del AFD mínimo que captura el lenguaje) tal que toda cadena mayor o igual resulta de haber realizado al menos un ciclo sobre uno de los estados del autómata. Esto es, si se tiene w = xyz, se obtiene un recorrido de la siguiente forma.

Lema de pumping

Notar que la cadena y debe ser no vacía para que el ciclo efectivamente exista, xy es menor que la cantidad de estados del autómata, y la cadena total debe superar la cantidad de estados (o podría ser capturada por el autómata sin efectuar ningún ciclo). Expresado en transiciones de configuraciones instantáneas:

$(q_{0},xyz)\vdash ^{*}(q_{i_{j}},yz)\vdash ^{*}(q_{i_{k}},z)\vdash ^{*}(q_{m},\lambda )$

Como $q_{i_{j}}=q_{i_{k}}$ y por la propiedad ya demostrada, es posible repetir y tantas veces como se desee y volver siempre al mismo estado, que tras consumir la cadena z se sabe que lleva a un estado final con lo que la cadena resulta aceptada.

El lema de pumping es una manera útil de demostrar que un lenguaje no es regular, viendo que no verifica este lema. Notar que la implicación no vale a la inversa, esto es, un lenguaje no regular puede cumplir pumping de regulares. En estos casos generalmente se recurre a demostrar que el complemento, inverso, unión o alguna combinación a partir de dicho lenguaje no lo verifica.

Minimizacion

Minimizacion se aplica solamente a AFD, no existe equivalente sobre AFND. Tambien es necesario que el AFD no tenga estados inalcanzables (debe haber un camino orientado desde el estado inicial hacia cualquier otro).

Se basa en el concepto de estados indistinguibles. Dos estados son indistinguibles sii para cualquier cadena, partiendo de esos estados se llega siempre o a finales o a no finales. Vale que los estados a los que se llegan son tambien indistinguibles. Indistinguibilidad es una relacion de equivalencia.

Indistinguibilidad de orden K

Es analogo a indistinguibilidad pero sujeto a cadenas de longitud a lo sumo K. Es el que se usa en la practica.

Relacion de equivalencia

Al igual que indistinguibilidad, es una relacion de equivalencia (reflexiva, simetrica y transitiva). La demostracion es trivial.

K+1 implica K

La relacion de orden K+1 esta contenida no estrictamente en la de orden K. Si dos estados son indistinguibles respecto de cadenas de longitud a lo sumo K+1, entonces, en particular, lo son para cadenas de longitud a lo sumo K.

Cociente por orden 0

El conjunto de estados de un automata, cocientado por la relacion de indistinguibildad de orden 0, lo separa en dos clases de equivalencia: los finales y los no finales.

K+1 sii K por todo terminal

Dos estados p y r son indistinguibles de orden K+1 sii para todo terminal a vale que los estados que se alcanzan a partir de consumir a por p y r son indistinguibles de orden K. Esto permite dar una definicion inductiva de indistinguibilidad.

La ida se prueba por absurdo. Si existe un terminal a tal que al consumirlo se llega a dos estados p' y r' distinguibles por alguna cadena alfa de longitud a lo sumo K, entonces la cadena a + alfa distingue K+1 a p y r, lo que contradice la hipotesis.

La vuelta tambien se puede probar por absurdo. Si p y r son distinguibles por alfa de longitud K+1, entonces p' y r' , alcanzados tras consumir el primer caracter de alfa, son distinguibles por el resto de alfa, que tiene longitud a lo sumo K, lo que contradice la hipotesis.

K+1 = K implica K+n = K

Si para cualquier par de estados q y p vale que la relacion de indistinguibilidad de orden K+1 es igual a la de orden K, entonces cualquier indistinguibilidad de orden superior seguira siendo igual. Esto da un criterio de corte para la definicion inductiva de indistinguibilidad de orden K, y permite generalizar de orden K a indistinguibilidad en general.

Puede demostrarse por induccion en n. El caso base es trivial. Para el paso inductivo, simplemente se usa que si dos estados son indistinguibles orden k+n+1, entonces los estados a los que se llega por cualquier terminal lo son orden k+n, y luego se aplica la hipotesis inductiva.

Intuitivamente, esto sucede pues indistinguibilidad de orden K permite distinguir a todos los estados que estan a "distancia" K de algun estado final. Al pasar a K+1, se agregan todos los estados que están a un paso más. Si no hay cambios, es porque ya se cubrieron todos los estados del automata, y no es necesario tener cadenas mas largas para distinguirlos.

Automata Minimo

Un automata minimo se logra tomando como estados las clases de equivalencia generadas por la relacion de indistinguibilidad en el automata original. Las transiciones en el nuevo automata se definen como $\delta \prime ([q],a)=[\delta (q,a)]$, es decir, el estado alcanzable en el AFDM a partir de la clase [q] por el terminal a, es la clase que se alcanza por a a partir de todos los estados que conforman q en el AFD original.

Transiciones entre clases indistinguibles

Dada la definicion de funcion de transicion anterior, vale la equivalencia tambien para la funcion de transicion extendida. Esto es, si en el AFD original se llegaba al estado r desde q por la cadena alfa, entonces en el minimo se llega a la clase de equivalencia de r desde q via alfa.

${\hat {\delta }}(q,a)=r\Longrightarrow {\hat {\delta }}\prime ([q],a)=[r]$

Se demuestra por induccion en la longitud de la cadena. El caso base (longitud cero) es trivial. Para el paso inductivo, se parte la cadena en a + alfa, y se aplica la definicion de la funcion no extendida (sobre a) junto con la hipotesis inductiva (sobre alfa), mas propiedades de la funcion de transicion extendida.

Cantidad de estados

Dados dos AFDs M y M', si para todo par de cadenas que conducen a estados diferentes en M desde q0 tambien conducen a estados diferentes en M' desde q0', entonces M' debe tener tantos o más estados que M.

Para demostrarlo, se puede obtener una funcion inyectiva de Q en Q', esto es, alguna funcion que para todo estado de Q vaya a un estado de Q' y no repita imagenes. Esto garantiza que $|Q|\leq |Q'|$.

Dicha funcion f(q) se puede definir como el estado que se alcanza en M' a desde q0' consumiendo la cadena g(q). La funcion g puede definirse como la menor cadena en M tal que al consumirla desde q0 se llegue al estado q; o sea, qué camino hay que seguir en M para llegar a q.

Como todas las cadenas generadas por g llevan a estados diferentes, entonces al consumirlas en M' tambien se llegan a estados diferentes (por hipotesis). Por lo tanto, se tiene la funcion inyectiva buscada.

Minimo

Se desea probar que el automata minimo construido a partir de las clases de equivalencia de la funcion de indistinguibilidad es efectivamente minimo. Esto es, que no existe ningun automata M' que reconozca el mismo lenguaje que MR (siendo MR el automata reducido) y que tenga menos estados.

Por la demostracion anterior, esto implica que deberia existir un par de cadenas alfa y beta tales que lleven a estados distintos p y r en MR y a estados iguales en M'.

Al ser p y r estados distintos en MR, significa que son distinguibles, esto es, que hay una cadena que lleva a uno a un estado final y a otro a uno no final. Esto significa que al concatenar esta cadena a las dos alfa y beta que habian dado origen a p y r, se obtienen dos cadenas, las cuales una pertenece al lenguaje y la otra no.

Ahora bien, como p y r coinciden en M', cualquier cadena los lleva al mismo estado, sea final o no. Entonces, al realizar la misma concatenacion que antes, se llega a ambas cadenas pertenecen o no. Por lo tanto, M' no reconoce el mismo lenguaje que MR, absurdo que proviene de suponer que MR no era minimo en cantidad de estados.

Lenguajes libres de contexto

Propiedades

Union

Si L1 y L2 son LIC, entonces L1 U L2 tambien lo es.

Dadas dos gramaticas que representen a los dos lenguajes que forman la union, basta con construir una nueva gramatica (suponiendo que la interseccion entre los no terminales es vacia) a partir de la union de los no terminales, terminales y producciones. Basta crear un nuevo simbolo distinguido S y producciones de la forma $S\rightarrow S_{1}$ y $S\rightarrow S_{2}$.

Concatenacion

Si L1 y L2 son LIC, entonces L1L2 tambien lo es.

La demostracion es analoga al caso anterior. Se construye una gramatica nueva uniendo los simbolos y producciones de G1 y G2, y se agrega un nuevo simbolo distinguido S con la produccion $S\rightarrow S_{1}S_{2}$.

Repeticion

Si L1 es LIC, entonces L1+ tambien lo es.

Para generar la gramatica que represente a L1+, basta añadir un nuevo simbolo distinguido S con las producciones $S\rightarrow S_{1}S$ y $S\rightarrow S_{1}$. Esto permite repetir el lenguaje tantas veces como se desee.

Interseccion

Si L1 y L2 son LIC, la interseccion puede no ser un lenguaje libre de contexto.

Un contraejemplo es tomar $L_{1}=\{a^{n}b^{m}c^{l}:n=m\}$ y $L_{2}=\{a^{n}b^{m}c^{l}:m=l\}$, ambos LIC, mientras que su interseccion $L=\{a^{n}b^{m}c^{l}:n=m=l\}$ no lo es.

Si L1 es LIC y L2 es regular, la interseccion es LIC

La demostracion es analoga a la interseccion de lenguajes regulares, con la excepcion de que se añade una pila al automata generado, la cual esta controlada por L1. Notar que una demostracion equivalente no funciona para dos libres de contexto, pues seria necesario mantener dos pilas en simultaneo.

Complemento

Si L es LIC, su complemento puede no ser un lenguaje libre de contexto

Suponiendo que lo fuera, entonces como la union preserva indepedencia del contexto, podria escribirse la interseccion como composicion de union y complementacion usando De Morgan, y se estaria probando que la interseccion de LICs genera LICs, lo cual ya se demostro que es falso.

Lenguajes {ww}

El lenguaje de la forma ww no es independiente de contexto

Sea el lenguaje $L=\{ww:w\in \Sigma ^{*}\}$, vale que L no es LIC. Puede demostrarse tomando el lenguaje L1 como la interseccion entre L y el lenguaje regular $a^{*}b^{*}a^{*}b^{*}$. Si L fuera LIC, entonces L1 tambien debiera serlo. Pero L1 resulta de la forma $a^{n}b^{m}a^{n}b^{m}$, que puede demostrarse por pumping que no es LIC.

Esto tiene como resultado que un lenguaje de programacion en el cual se use declaracion de variables no basta una gramatica independiente de contexto para especificarlo, pues no hay manera de reconocer, dado el uso de una variable, si esta ya fue declarada o no.

Lema de Pumping (LIC)

Altura del árbol

La altura del árbol de derivación es la longitud del camino más largo en el árbol de derivación tal que comienza en la raíz y el final es una hoja (definicion natural de arbol). Vale que la hoja siempre es un terminal o $\lambda$. Notar que en el árbol de derivación, la base (hojas leídas en preorder) es igual a la cadena derivada.

Sea una gramatica donde $a$ es la longitud del lado derecho más largo entre todas las producciones. Dado un árbol T para una cadena $\alpha$, vale que $|\alpha |\leq a^{h}$, donde $h$ es la altura del arbol.

La demostración se hace por inducción sobre la altura. El caso base con h = 0 es trivial ($\alpha =S\implies |\alpha |=1\leq a^{0}=1$). El paso inductivo para $h+1$ se basa en que la base correspondiente a la altura $h$, llamémosla $\gamma$, cumple la HI; y como $\alpha$ se deriva a partir de $\gamma$ expandiendo a lo sumo $|\gamma |$ simbolos no terminales, entonces $|\alpha |\leq a*|\gamma |\leq a*a^{h}=a^{h+1}$.

Pumping (LIC)

El lema de pumping para LIC es similar al de gramaticas regulares. La idea es que para toda cadena que supere una longitud critica n del lenguaje (puede tomarse $a^{|V_{N}|+1}$), la cadena pueda descomponerse en 5 partes r,x,y,z,s tal que puedan insertarse tantas repeticiones de x y z como se desee y que la cadena se mantenga en el lenguaje. Se pide ademas que la longitud de x+z sea no nula (para que haya algo a insertar) y que x+y+z no supere a n.

Decimos que un árbol de derivación mínimo T para la cadena $\alpha$ es uno de altura mínima tal que no existe otro de la misma altura que tenga menos derivaciones. La demostración parte de un árbol T mínimo para una cadena $\alpha$ con $|\alpha |\geq n$. Usando el lema anterior, puede probarse que $a^{h}\geq |\alpha |\geq n=a^{|V_{N}|+1}$, lo que lleva a que $h\geq |V_{N}|+1$.

En otras palabras, si la cadena es lo suficientemente grande, entonces la altura del arbol que la genera sera mayor estricto a la cantidad de simbolos no terminales que tiene la gramatica. Por lo tanto, recorriendo la rama mas larga del arbol, debe haber por lo menos un no terminal repetido (supongamos A).

Se considera entonces que la aparicion mas baja de A genera la cadena y, mientras que la siguiente genera xyz (lease vwx en la figura).

Esto significa que A deriva (en uno o mas pasos) tanto en y como en xyz, y que S deriva en rAs. Haciendo induccion en la cantidad de apariciones de x y z (caso base es cero) es sencillo ver que A termina derivando en xAz o y, con lo que $rx^{i}yz^{i}s$ es forma sentencial del lenguaje.

Nos falta ver que $|xz|>0$. Llamemos $A_{2}$ a la aparición más baja de A, y $A_{1}$ a la que le precede. Supongamos que $|xz|=0$. Esto quiere decir que podríamos reemplazar el subárbol con raíz en $A_{1}$ por el árbol con raíz en $A_{2}$ y tener un árbol T' que genera la misma cadena $\alpha$. Como $A_{2}$ ocurre después que $A_{1}$, T' tendría menos derivaciones que T. Pero dijimos que T es un árbol mínimo. Absurdo, que vino de suponer que $|xz|=0$.

NOTA: Un detalle importante que se toma en el final (y que no queda tan claro en los apuntes) es la justificación de que $|xyz|\leq a^{|V_{N}|+1}$ (en el dibujo es vwx). La respuesta es sencilla, recorremos el árbol de abajo hacia arriba buscando la segunda aparición de A, la cantidad MÁXIMA de no terminales por los que tenemos que pasar hasta encontrar el primer repetido es $|V_{N}|+1$. Esa es la justificación por la que podemos afirmar que ese subárbol tiene esa altura y de ahí acotar la longitud de $xyz$.

Decidibilidad

Los siguientes problemas sobre lenguajes libres de contexto no son decidibles:

• Dada una gramatica libre de contexto, es ambigua?
• Dado un LIC, existe una gramatica que lo represente que no sea ambigua?
• Es la interseccion de dos LIC vacia?
• Son dos LICs iguales?
• Dado un LIC, es igual a Sigma*, donde Sigma es el alfabeto?

Equivalencias

Automata a Gramatica

La conversion de automata a gramatica se hace a partir de un automata por pila vacia. Se basa en la construccion de simbolos no terminales de la forma [q,A,p], tal que cada no terminal asi definido genera las cadenas w tal que implican que en el automata se haga pop de A en el stack (y de todos los demas simbolos que genero A) y se pase al estado p. En otras palabras, $[q,A,p]\Rightarrow _{G}^{*}x\Longleftrightarrow (q,x,A)\vdash _{M}^{*}(p,\lambda ,\lambda )$.

Las producciones de la gramatica se construyen, entonces, de la siguiente manera:

• $S\rightarrow [q_{0},Z_{0},q]$, siendo q todos los estados posibles. Esto significa generar todas las cadenas que comienzan en en el estado inicial, sacan Z0 de la pila (dejandola vacia) y terminan en cualquier estado. Es decir, todas las cadenas q acepta el automata.

• $[q,A,q_{m+1}]\rightarrow a[q_{1},B_{1},q_{2}][q_{2},B_{2},q_{3}]\ldots [q_{m},B_{m},q_{m+1}]$ sii $(q_{1},B_{1}\ldots B_{m})\in \delta (q,a,A)$. Los estados q2,q3... distintos del inicial y final son cualquier combinacion de estados del automata. Esto genera, dada una transicion de un estado a otro cambiando A por una secuencia de simbolos B, todos los posibles caminos entre estados que permiten hacer pop de cada uno de los B. Es decir, para ir de un estado q a otro p haciendo pop de A, se hacen todos los caminos posibles de q a p haciendo pop de cada uno de los simbolos que se generaron a partir de A.

Notar que en la segunda regla, a podria ser lambda, y la secuencia de B podria ser vacia si la transicion que consume a A del tope del stack no pushea ningun simbolo. En ese caso se reemplaza la secuencia de no terminales por lambda.

Para demostrar la vuelta de la doble implicacion, es decir, que $(q,x,A)\vdash _{M}^{i}(p,\lambda ,\lambda )\Longrightarrow [q,A,p]\Rightarrow _{G}^{*}x$, se hace induccion sobre i, o sea, la cantidad de pasos que se dan en el automata para vaciar la pila consumiendo la cadena x.

El caso base (i = 1, es decir, la cadena es un terminal o lambda) es trivial a partir de las reglas para construir las producciones. El paso inductivo separa a x en a + y, siendo a un terminal o lambda, y y el resto de la cadena. En un primer paso, se consume A del stack y a de la entrada y se reemplaza A por una sucesion de simbolos B. Cada uno de estos B deriva, en menos de i pasos del automata, en un pedazo de la cadena y.

Entonces, por hipotesis inductiva, se puede hacer el salto a la gramatica, y se llega a que cada uno de los $[q_{j},B,q_{j+1}]$ que conforman la produccion con lado izquierdo [q,A,p] genera un pedazo de y. Entonces el lado derecho construido para el [q,A,p] de la tesis deriva efectivamente en a + y, o sea, x.

La ida, $[q,A,p]\Rightarrow _{G}^{i}x\Longrightarrow (q,x,A)\vdash _{M}^{*}(p,\lambda ,\lambda )$, se prueba de manera similar. El caso base, con la cadena x igual a a, siendo a un terminal o lambda, se prueba directo a partir de las reglas.

El paso inductivo requiere partir la cadena x en a + x1 + x2 +...+xn, tal que cada uno de los xi se deriva a partir de cada simbolo $[q_{j},B,q_{j+1}]$ que aparece luego de la primera derivacion. Como estos alcanzan cada xi en menos de i pasos, vale la HI, y se puede hacer el salto al automata, en particular, instanciando los qj en los estados que recorre el automata para vaciar la pila.

Gramatica a Automata

Para pasar de una gramatica a un AP, se genera un AP por pila vacia de un solo estado, que represente las derivaciones mas a la izquierda generadas por la gramatica. Tener en cuenta que cualquier forma sentencial no terminal generada a partir de derivaciones mas a la izquierda puede representarse como $xA\alpha$, donde x es un string de terminales, y $A\alpha$ es la cola (de ahora en mas y), con A no terminal y $\alpha$ conjunto de terminales y no terminales.

La idea es que el automata comience con el simbolo distinguido S de la gramatica en la pila, y a cada paso tome una decision basado en el tope de la pila exclusivamente (pues hay un solo estado).

• Si en el tope de la pila hay un no terminal, entonces lo reemplaza no deterministicamente por alguna de sus producciones. Esto es, si $A\rightarrow \alpha$ en la gramatica, entonces $(q,\alpha )\in \delta (q,\lambda ,A)$ en el automata.

• Si en el tope de la pila hay un terminal, se matchea con la entrada y se hace pop del stack. Es decir, que para todo terminal, $\delta (q,a,a)=\{(q,\lambda )\}$. Así, el automata consume todos los terminales que va apilando (que son parte de x en la forma sentencial) hasta llegar al primer no terminal A de la cola y reemplazarlo por alguna de sus producciones.

Para probar que los lenguajes son equivalentes, es decir, que $S\Rightarrow ^{+}w\Longleftrightarrow (q,w,S)\vdash ^{+}(q,\lambda ,\lambda )$, se prueba como resultado intermedio más general que $A\Rightarrow ^{m}w\Longleftrightarrow (q,w,A)\vdash ^{n}(q,\lambda ,\lambda )$.

La ida se prueba por induccion sobre m, es decir, sobre la cantidad de producciones que se aplican para llegar de A a w. El caso base (1) es trivial a partir de las definiciones, pues la unica derivacion posible es A en lambda.

Para el paso inductivo se supone que A se deriva en $X_{1}\ldots X_{k}$ en un primer paso, y para los m-1 restantes (es decir, cada uno de los X) se puede aplicar hipotesis inductiva y se obtiene el string de terminales correspondientes. El primer paso es el unico que basta probar entonces, y sale directo a partir de la primer regla.

La vuelta, $A\Rightarrow ^{m}w\Longleftarrow (q,w,A)\vdash ^{n}(q,\lambda ,\lambda )$ tambien se hace por induccion. El caso base (n = 1) nuevamente es trivial, pues implica que w sea la cadena vacia y la produccion que la genera sea A en lambda.

El paso inductivo es similar al de la ida. Se observa que A genera $X_{1}\ldots X_{k}$ en un paso por la regla 1, y los X entonces generaran los strings correspondientes para formar w (por hipotesis inductiva). Por lo tanto, A genera w.

Automata por estado final a pila vacia

La construccion de un automata por pila vacia (PV) a partir de un automata por estado final (EF) es sencilla. Basta con agregar dos estados nuevos al automata, uno inicial y otro que servira de final para vaciar el stack.

Primero se agrega un nuevo simbolo para el comienzo del stack, llamemoslo X0, y se agrega por debajo de la configuracion inicial original (supongamos Z0) mediante una transicion lambda de un nuevo estado $q_{0}\prime$ al original $q_{0}$.

Esto impide que el automata original EF pueda vaciar su pila accidentalmente y terminar, caso en el que deberia rechazar la cadena, y un equivalente por PV entonces la aceptaria.

Para simular la aceptacion, se agregan transiciones lambdas de todos los estados finales del automata original a un nuevo estado qf. Este estado no consume simbolos de la entrada y se limita a vaciar la pila. Asi, cuando el automata original llega a un estado final, puede seguir moviendose por el automata o vaciar la pila y aceptar (si no queda mas input).

Para probar que el lenguaje generado por PV incluye al de EF se debe probar que si una cadena x pertenece a EF, entonces pertenece a PV. Basta usar configuraciones instantaneas y ver que si $(q_{0},x,Z_{0})\vdash _{EF}^{*}(q,\lambda ,\gamma )(q\in F)$ entonces en PV vale $(q_{0},x,Z_{0}X_{0})\vdash _{PV}^{*}(q,\lambda ,\gamma X_{0})$. Esto significa que si en EF se llega a un estado final con cierta configuracion en la pila habiendo consumido toda la entrada, en PV se llega al mismo estado pero con X0 en la base de la pila.

La vuelta se prueba de la misma forma.

Automata por pila vacia a estado final

La construccion de un automata por EF a partir de uno por PV es similar al caso anterior, en el que se agrega un nuevo estado inicial y un nuevo estado final. Del nuevo estado inicial al inicial del PV se va por una transicion lambda que agrega un nuevo simbolo en la base de la pila (digamos X0) de la misma forma que antes.

Sin embargo, como ahora no hay estados finales (puesto que PV acepta por pila vacia), se generan transiciones lambda desde todos los estados del PV original al nuevo estado final $q_{f}$. Estas transiciones requieren que esté el simbolo X0 en el tope de la pila, lo que equivale a decir que el PV original vacio la pila aceptando la cadena de entrada. El X0 entonces se agrega para que la pila no se vacie y sea posible moverse al estado final.

La demostracion es analoga al caso anterior.

Lenguajes deterministicos

Un lenguaje libre de contexto deterministico es aquel que puede reconocerse mediante un automata de pila deterministico. Un automata de pila deterministico debe cumplir que en cualquier estado, dado un terminal a consumir y un tope de la pila determinados, haya una unica transicion posible a realizar.

Para que se verifique esto, basta con que para cualquier 3-upla (q,a,Z) (estado, terminal, tope de pila) el conjunto determinado por $\delta (q,a,Z)$ sea de cardinal a lo sumo 1. Tambien debe cumplirse que si un estado tiene una transicion lambda dado un tope de pila Z, entonces no puede tener ninguna otra transicion por ese mismo tope de pila, cualquiera sea el terminal.

Equivalencias

Los lenguajes libres de contexto deterministicos estan incluidos de manera estricta en los libres de contexto. Un ejemplo es el lenguaje $ww^{r}$ (es decir, una cadena seguida de su reverso). Intuitivamente, no puede parsearse con un APD pues el automata no tiene manera de saber cuando termino w y cuando comienza su reverso. Como nota de color, esto puede salvarse introduciendo un caracter $ en el momento en que termina w y comienza el reverso, haciendo el lenguaje deterministico.

Logicamente, los LICD incluyen a los lenguajes regulares, ya que un APD por estado final no es mas que un AFD en el que no se tiene en cuenta el manejo de la pila.

Ademas, si bien en los automatas de pila estandar un automata por pila vacia es equivalente a uno por estado final, en el caso de los deterministicos la equivalencia no se mantiene. Un APD por pila vacia puede representar un lenguaje L solamente si este lenguaje es libre de prefijos.

Notar que un lenguaje sencillo como ser a* es regular, pero no es libre de prefijos, con lo cual el APD por pila vacia no puede reconocerlo. Esto hace que los APD por pila vacia sean menos poderosos que por estado final. Sin embargo, la propiedad del prefijo es lo unico que los diferencia. Vale que si se tiene un lenguaje L reconocible por un APD por estado final, y L es libre de prefijos, entonces L es reconocible por un APD por pila vacia.

Esta limitacion no es tan grave ya que para cualquier lenguaje se puede generar otro similar que sea libre de prefijos simplemente agregando un caracter terminal $ al final.

Los LICD siempre tienen gramaticas no ambiguas que los representan, aunque la vuelta no siempre es cierta. Es decir, puede haber una gramatica no ambigua libre de contexto que no tiene APD que la represente.

Consumir cadena de entrada

Vale que para cualquier APD M, existe otro APD M' equivalente (por estado final) tal que M' siempre consume la cadena de entrada. Notar que este problema no existía en los lenguajes regulares. Ahora, un autómata puede no consumir por completo la cadena de entrada pues puede bloquearse al llegar a un estado del que ninguna transición es posible, o entrar en un loop infinito de lambdas, o vaciarse su stack.

Esto no sucedía en los finitos pues no había transiciones lambda, y desde cualquier estado siempre había una transición por cualquier terminal hacia otro estado (aunque fuera un estado trampa). Así, un AFD siempre consumía toda la entrada, y aceptaba sii terminaba en un estado final. En un APD puede suceder que la cadena no se consuma enteramente (caso en el cual es rechazada).

Para construir el APD M' se agregan tres nuevos estados. Primero un nuevo estado inicial q0' con una única transición lambda al original q0, tal que agrega una nueva base X0 en la pila, por debajo de Z0. Esto asegura que en ningún caso el autómata se frena por pila vacía.

El segundo estado que se agrega es un estado trampa d. Dado cualquier estado que para un tope de pila no tenga transiciones lambda, se agrega una transición por cada terminal no contemplado hacia el estado trampa. Esto permite que el autómata no se bloquee por falta de transiciones. La condición de que no haya transiciones lambda es para no romper el determinismo. A su vez, se agregan loops sobre el estado trampa para todos los terminales y símbolos de la pila.

También se agregan transiciones lambda desde todos los estados con tope de pila X0 hacia el estado trampa, para capturar los casos en los que el autómata M hubiera frenado por pila vacía.

Lo último que resta por eliminar son los loops lambda, definidos tal que para todo i existen estados $q_{i},\gamma _{i}$ tales que $(q,\lambda ,Z)\vdash ^{i}(q_{i},\lambda ,\gamma _{i})$. Si existe algún estado final en el ciclo, entonces se redefine la transición lambda a partir de q por Z tal que vaya a un nuevo estado final f (del cual se construyen transiciones lambda hacia el trampa, por si era necesario consumir más input) haciendo pop del stack. Si ninguno en el ciclo era final, se redefine para que vaya al trampa, también haciendo pop del stack.

Complementacion

Vale que los LLCD son cerrados respecto de la complementación. Sin embargo, para construir un APD M' que capture el complemento de M, no basta con invertir finales con no finales como sucedía en los regulares. Puede suceder que el autómata M no consuma por completo la cadena de entrada w, por lo tanto ni M ni M' (construido invirtiendo finales y no finales) la reconocerían, pues ambos se bloquearían o entrarían en un loop lambda.

Aún solucionado esto, teniendo un autómata que consuma toda la entrada (lo cual es posible de construir), puede suceder que en M la cadena termine en un estado final q con una transición lambda hacia un no final p; con lo cual M' también reconocería esa cadena pues al terminar en q podría pasar a p y reconocerla.

La construcción de M' se hace entonces a partir de un M que consume toda la entrada, y debe solucionar el problema de quedar en un estado con lambdas hacia estados distintos.

Cada estado de M' es de la foma [q,k], donde q es un estado de M y k es un entero que vale 1, 2 o 3. Los estados finales de M' son todos aquellos con k = 3, y el inicial es [q0,k] con k = 1 si q0 es final o k = 2 si no.

La intuición detrás de k es que detecta si entre transiciones sin consumo de entrada se ha pasado por un estado final. Si se pasó por un final, vale 1, si no, 2.

La función de transición se define de tal forma que si se hace a través de un lambda desde un estado q hacia un estado p, entonces se va a [p,1] si p es final en M o el q de M' tenía k = 1 (es decir, se encontró con un estado final o venía de un final pasando por lambdas), o a [p,2] si no (no hay finales en el camino).

Si la transición se hace de q a p consumiendo un terminal a, entonces primero se permite hacer un salto hacia [q,3] por lambda desde [q,2]. Esto permite finalizar si ya se consume toda la cadena. Luego, desde [q,1] y [q,3] se agregan transiciones a p por a, yendo a [p,1] si p es final, o a [p,2] si no lo es.

Resumiendo, la idea es mantener tres niveles en el autómata, uno de los cuales contiene los estados finales (3), el otro los estados alcanzados a través de una transición lambda que pasaron por un final (2) y el último los no alcanzados por lambda desde un final (1).

Máquinas de Turing

Las máquinas de Turing se definen como un autómata con una cinta infinita a derecha (es decir, las celdas van de cero a infinito positivo) con la siguiente aridad:

$MT=<Q,\Gamma ,B,\Sigma ,\delta ,q_{0},F>$

• $Q$ conjunto de estados
• $\Gamma$ alfabeto de la cinta
• $B\in \Gamma$ símbolo blanco, representa una celda vacía
• $\Sigma \subset \Gamma$ alfabeto de entrada, no incluye al blanco
• $\delta :Q\times \Gamma \rightarrow partes(Q\times \Gamma \times \{L,R\})$ acciones
• $q_{0}\in Q$ estado inicial
• $F\subseteq Q$ estados finales

Las acciones de la máquina dependen del estado actual y del símbolo que hay bajo la cabeza lectora/escritora, e implican escribir otro símbolo (puede ser el mismo) y moverse a izquierda o derecha.

La configuración instantánea de una máquina de Turing se define como $\alpha _{1}q\alpha _{2}$, donde $\alpha _{1}$ es el contenido de la cinta (sucesión de caracteres) a la izquierda del cabezal, q es el estado actual de la máquina, y $\alpha _{2}$ es el contenido de la cinta desde el cabezal hasta el último símbolo distinto de blanco. Así, se puede especificar cuál es el estado actual, el contenido de la cinta y la posición del cabezal.

La cinta inicialmente comienza llena de blancos, excepto al comienzo donde tiene escrito el input a reconocer. Notar que el caracter blanco no puede pertenecer al alfabeto de entrada.

La máquina acepta una cadena si en su ejecución llega a un estado final, notar que la máquina no tiene transiciones desde un estado final. Como la cadena está escrita en la cinta, no existe el concepto de consumir la cadena de entrada.

Máquina de Turing determinística

Una máquina de Turing es determinística cuando dado un estado y un símbolo bajo el cabezal existe una única acción. Vale que una máquina determinística puede emular a una no determinística.

Para esto se construye una MTD M' que reconoce la cadena cuando esta pertenece al lenguaje y se cuelga cuando no pertenece. La MTD construida tiene tres cintas (se puede demostrar que una máquina con un número finito de cintas equivale a una de una sola cinta). La idea es guardar en la primer cinta la cadena de entrada, en la segunda un número que simboliza una traza a seguir de la máquina M original, y la tercera usarla para emular las operaciones de M.

Para simbolizar una traza, se calcula el máximo grado de salida (r) de los nodos de la máquina M, se numera cada transición a partir de cada estado con un número de 1 a r, y se escribe una secuencia de dígitos entre 1 y r. Esto permite recorrer todas las posibles secuencias de configuraciones instantáneas en BFS.

La MTD M', entonces, en cada iteración copia la entrada de la primer cinta a la tercera, incrementa en 1 el valor de la segunda cinta (número expresado en base r que simboliza la traza) y con esa traza emula a M sobre la tercer cinta. Si termina en estado de aceptación, se acepta la cadena. Si se traba o termina en un estado no final, se itera nuevamente.

Lenguajes Recursivamente Enumerables

Los LRE (lenguajes tipo 0 en la jerarquía de Chomsky) son lenguajes reconocibles por una máquina de Turing. Son aquellos que pueden especificarse sin restricciones sobre sus producciones.

Gramática a MTND

Para pasar de una gramática tipo 0 a una MTND, se utilizan dos cintas. En la primera se guarda la cadena; en la segunda se van generando formas sentenciales de manera no determinística a partir del símbolo distinguido S. Cuando se encuentra alguna que matchea la entrada, se acepta; si no, la máquina se cuelga.

MT a Gramática

Para pasar de una MT a una gramática se establece una equivalencia entre los símbolos de la gramática y las configuraciones instantáneas de la máquina de Turing. Los símbolos generados son de la forma [a,b], donde a representará el caracter original de la cadena de entrada y b el caracter sobre el que opera la máquina.

Se proveen producciones para generar, incialmente, una cadena arbitraria de símbolos [a,a], siendo a cualquier terminal. Esto equivale a tener inicialmente en la cinta cualquier cadena. Seguidos a estos se genera una cantidad libre de simbolos [lambda,Blanco], tantos como necesitaría la cinta para operar.

La gramática genera, al principio de todo, un caracter q que representará el cabezal de la máquina. Las producciones de la gramática permiten "mover" q entre los símbolos [a,b] (modificando solamente los b) en base a las acciones permitidas por la MT original.

Una vez alcanzado un estado final, se generan producciones que eliminan todos los símbolos [a,b] dejando solamente los a correspondientes a la cadena original, y finalmente a q. Así, la cadena final de terminales es la cadena a generar.

Lenguajes Sensitivos al Contexto

Los lenguajes dependientes del contexto se expresan con gramáticas tipo 1 en la jerarquía de Chomsky, que tienen la restricción de que la longitud del lado derecho de una producción no puede ser menor a la del lado izquierdo.

Autómata Linealmente Acotado

Los ALA pueden verse como máquinas de Turing con la cinta acotada. En un ALA el alfabeto de entrada incluye dos símbolos, usados como tope de entrada y tope de salida. El autómata no puede moverse más allá de los topes ni sobreescribirlos.

Notar que un ALA tal que en la cinta tenga una cantidad de blancos lineal a la longitud de la entrada es equivalente a un ALA con cero blancos, que opera exclusivamente sobre la cadena de entrada.

A diferencia de lo que sucedía con las MT, no hay equivalencia entre ALA y ALAD. A primera vista puede observarse que el método anterior no funciona pues el número que simboliza la traza a emular (en la segunda cinta) puede crecer arbitrariamente.

Gramática a ALA

La equivalencia entre una gramática sensitiva al contexto y un ALA se demuestra exactamente igual que para máquinas de Turing en general, excepto que en este caso puede agregarse la restricción de que si la cadena que se está generando excede el tamaño de la que se ha de reconocer se corta esa rama (pues ninguna cadena de terminales y no terminales puede derivar en una de longitud menor). Así la cantidad de posibilidades a explorar es finita.

Lenguajes Recursivos

Los lenguajes recursivos se encuentran estrictamente entre los sensitivos al contexto y los recursivamente enumerables. Son aquellos reconocibles por una HTM (halting Turing machine). Es decir, existe una máquina de Turing que dada cualquier entrada, siempre para y devuelve si una cadena pertenece o no (no puede colgarse).

Inclusión de Sensitivos al Contexto

Para demostrar que los LSC están incluidos dentro de los recursivos, se construye una HTM que determine si una cadena pertenece al lenguaje. Dada una gramática GSC y una cadena de entrada w de longitud n, se construye un grafo finito donde cada nodo es un string de terminales y no terminales de longitud menor o igual a n.

Los arcos en este grafo representan si es posible ir de un string a otro mediante derivaciones de la gramática. Notar que este grafo es finito y puede construirse mediante un algoritmo.

Luego, para determinar si una cadena w pertenece al lenguaje, simplemente se verifica mediante un algoritmo si existe un camino desde S hasta el nodo que contiene a w. Como lo anterior es un algoritmo (siempre termina) existe una HTM que lo ejecuta, con lo cual el lenguaje LSC es recursivo.

Lenguaje Recursivo no LSC

Para demostrar que existe un lenguaje recursivo no sensitivo al contexto se utiliza un argumento diagonal. Primero se prueba un lema que indica que dada cualquier enumeración de HTMs, existe un lenguaje recursivo que no es aceptado por ninguna de ellas (el lenguaje que dada la cadena i, la acepta sii no es reconocida por la iesima HTM de la enumeración).

Eventualmente se llega a una contradicción, pues si existe una HTM de índice i en la enumeración, la cadena i debe ser reconocida por dicha HTM sii no lo es. Notar que este lenguaje es recursivo, pues existe un algoritmo (procedimiento que siempre termina) que puede determinar si una cadena i pertenece al conjunto: simplemente corre la HTM i con esa cadena y devuelve la negación.

A partir de esto, se construye una enumeración de las HTM que reconocen todos los LSC, lo cual es posible ya que se pueden enumerar las GSCs. Pero por el lema anterior existe un lenguaje que no es reconocido por ninguna de estas HTMs, es decir, por ningún LSC. Y este lenguaje es recursivo.

La demostración parece basarse en que el conjunto de HTMs no es Recursivamente Enumerable, mientras que el de GSCs sí lo es. Por lo tanto debe existir alguna HTM que genere un lenguaje no sensitivo al contexto.

Lenguaje Diagonal

El lenguaje diagonal es un ejemplo de un lenguaje que no es recursivamente enumerable. Requiere enumerar las MT y entradas posibles y llegar a una contradicción similar a la del problema de la parada.

Más formalmente, se basa en construir una tabla infinita de dos entradas. La celda (i,j) entonces vale 1 sii la máquina de Turing de nro j reconoce la cadena i. La MT se encuentra codificada en binario, y la cadena de entrada es de 0s y 1s.

Entonces, puede construirse el lenguaje de las cadenas i tal que no pertenecen a la MT de igual número (lenguaje diagonal). Si este lenguaje es recursivamente enumerable, entonces existe una MT Mk tal que reconce sus cadenas. En otras palabras,

$w_{k}\in L_{d}\Longleftrightarrow w_{k}\not \in L(M_{k})=L_{d}$

Con lo que se llega a una contradicción. La cadena de igual número que M es reconocida por la máquina sii no es reconocida.

Otra opción (distinta a la del pdf, revisar) es un lenguaje que acepta una cadena sii esta representa una máquina de Turing con una entrada dada, y dicha máquina para. Si dicha máquina existiera, resolvería el halting problem, lo que no es posible.

Lenguaje Universal

El lenguaje universal es el que se corresponde a la MT que ejecuta cualquier otra MT con cualquier entrada. En otras palabras, toma pares de cadena y MT, y determina si la cadena es reconocida por esa MT.

Recursivamente Enumerable

Este lenguaje es recursivamente enumerable. Puede construirse una MT con 3 cintas, de las cuales la primera contiene el input (la MT M más la cadena de entrada w), la segunda (inicializada con la cadena w) emula la cinta de M, y la tercera permite llevar cuenta del estado en el que se encuentra la M emulada.

No Recursivo

Para demostrar que este lenguaje no es recursivo, se supone inicialmente que lo es y se intenta llegar al absurdo. Para esto, se construye un algoritmo (es decir, un procedimiento que siempre para, emulable por una HTM) que dada una cadena de entrada, genera su MT con igual número. Luego se determina, usando la HTM del lenguaje universal (supusimos que era recursivo) si $(w_{i},MT_{i})$ es aceptado, esto es, si la máquina i acepta la cadena i.

Notar que este es el complemento del lenguaje diagonal. Como es un algoritmo, siempre termina y devuelve verdadero o falso. Con lo que puede generarse fácilmente una HTM que reconozca el lenguaje diagonal directamente. Lo que es absurdo puesto que no es siquiera recursivamente enumerable.

Intuitivamente, el que el lenguaje universal sea recursivo significaría que es posible tener un método que siempre termina que resuelve (por sí o por no) la pertenencia de cualquier cadena a cualquier MT. Es decir, es capaz de decidir el halting problem.

Analizadores Sintácticos Descendentes

Reescritura

Simbolos anulables

Un símbolo es anulable sii deriva en uno o más pasos en lambda. Una gramática no tiene símbolos anulables sii la única producción con lado derecho lambda es del símbolo distinguido, y éste no aparece en ningún lado derecho.

Renombramientos

Un renombramiento es una producción de la forma $A\rightarrow B$.

Simbolos inactivos

Un símbolo es activo sii deriva en una cadena de terminales.

Simbolos inalcanzables

Un símbolo es alcanzable sii aparece en alguna derivación a partir del símbolo distinguido, es decir, $S\Rightarrow ^{+}\alpha A\beta$.

Orden de aplicación

Todos los casos anteriores son salvables mediante un algoritmo, es decir, hay algoritmos para generar una gramática G' a partir de G tal que G' no tenga símbolos anulables, ni renombramientos, ni símbolos inactivos, ni símbolos inalcanzables. El orden de aplicación de los algoritmos es el aquí expuesto.

Analizador Descendente con Retroceso

El analizador descendente con retroceso (o backtracking) comienza a partir del simbolo distinguido generando formas sentenciales más a izquierda e intentando matchear con la entrada, haciendo backtracking si no lo logra. Equivale a pensar en un parser no deterministico.

Tiene el problema de que, como todos los parsers descendentes, no soporta gramáticas recursivas a izquierda, pues entra en una expansión infinita. Además, el backtracking (o no determinismo) hace que el tiempo que requiere para parsear una expresión sea inadmisible.

Analizador Descendente Predictivo

El objetivo de un analizador descendente predictivo es eliminar el no determinismo del anterior sabiendo siempre de alguna manera qué producción expandir para el no terminal más a la izquierda. Para esto se utilizan los símbolos directrices de cada producción.

Gramática LL(1)

Una gramática es LL(1) sii para toda producción con el mismo lado izquierdo (es decir, para toda expansión de un mismo no terminal) la intersección de los símbolos directrices es vacía. Esto permite decidir siempre, dado un no terminal y un token del input, cuál producción elegir para expandir.

Dada una gramática G, una gramática ampliada G' es una nueva gramática en la que se le añade a cada cadena un terminal de finalización, mediante una nueva producción $S'\rightarrow S\#$. Asimismo, una gramática reducida es aquella en la que todos sus no terminales son alcanzables y activos.

Propiedades de LL(1)

Dada una gramática G ampliada y reducida, vale que siguientes de todo no terminal es un conjunto no vacío.

Esto vale pues, como G es reducida, entonces para cualquier no terminal U vale que $\alpha U\beta \#$ es una forma sentencial. Por lo tanto, el conjunto de siguientes de U es igual al de primeros de beta. Si este es vacío, entonces siguientes de U es igual al símbolo #.

Dada una gramática G ampliada y reducida, si G es LL(1) entonces no es recursiva a izquierda.

La intuición detrás de este teorema viene dada por su contrarreciproco. Ningún parser descendente soporta gramáticas recursivas a izquierda, pues como trabaja con derivaciones más a la izquierda, puede entrar en loop al expandir siempre el mismo no terminal.

Se demuestra por el absurdo. Si es recursiva a izquierda, entonces existe un no terminal A tal que $A\rightarrow ^{+}A\alpha$, pero como A debe ser activo, entonces también vale que $A\rightarrow ^{+}\beta ,\beta \in V^{t}$. Por lo tanto, tienen que suceder:

• $A_{0}\rightarrow A_{1}\alpha _{1}\rightarrow A_{2}\alpha _{2}\alpha _{1}\rightarrow \ldots \rightarrow A_{k}\alpha _{k}\ldots \alpha _{1}$, donde A0 y Ak son el símbolo A.
• $A_{0}'\rightarrow A_{1}'\alpha _{1}'\rightarrow A_{2}'\alpha _{2}'\alpha _{1}'\rightarrow \ldots \rightarrow \beta$, donde A0' es el símbolo A.

En otras palabras, A deriva en dos cadenas distintas de las cuales una comienza nuevamente con A (donde se da la recursividad a izquierda) y otra es una cadena de terminales del lenguaje (pues A debia ser activo).

Luego, se considera el primer valor i tal que $A_{i-1}=A_{i-1}'$ pero $A_{i}\neq A_{i}'$, es decir, el punto en el que las dos derivaciones anteriores se diferencian, al usar las producciones:

• $A_{i-1}=A_{i-1}'\rightarrow A_{i}\alpha _{i}$ (1)
• $A_{i-1}=A_{i-1}'\rightarrow A_{i}'\alpha _{i}'$ (2)

El objetivo de la demostración será probar que ambas cadenas comparten alguno de sus símbolos directrices, con lo que la gramática no sería LL(1) y esto contradice la hipótesis.

Intuitivamente, esto se logra reemplazando el Ak de la primer cadena por beta, con lo los símbolos directrices de ambas producciones (1 y 2) serán o bien primeros de beta o bien siguientes de $A_{i-1}$.

En el caso en que la cadena beta sea no vacía, es posible descomponerla en $\beta =a\gamma$. Por lo tanto, los símbolos directrices de la cadena (2), es decir, la que deriva en beta, contienen a a. Pero entonces la cadena recursiva a izquierda puede reescribirse reemplazando el último Ak por beta: $A_{0}\rightarrow A_{1}\alpha _{1}\rightarrow A_{2}\alpha _{2}\alpha _{1}\rightarrow \ldots \rightarrow A_{k}\alpha _{k}\ldots \alpha _{1}\rightarrow \ldots \rightarrow a\gamma \alpha _{k}\ldots \alpha _{1}$.

Por lo tanto, los símbolos directrices de la producción (1) también contienen a a, con lo que la intersección de los directrices de ambas producciones es no vacía, con lo que la gramática no es LL(1), lo que es absurdo.

En el caso de que beta sea vacía, esto es, el símbolo A es anulable, vale que cada uno de los $A_{i}'$ y $\alpha _{i}'$ lo son, con lo que los símbolos directrices de la producción (2) incluyen a siguientes de $A_{i-1}$.

Además, vale que puede completarse la primer secuencia de derivaciones de manera similar a como se hizo en el caso anterior, pero este caso cambiando al último Ak por la cadena vacía: $A_{0}\rightarrow A_{1}\alpha _{1}\rightarrow A_{2}\alpha _{2}\alpha _{1}\rightarrow \ldots \rightarrow A_{k}\alpha _{k}\ldots \alpha _{1}\rightarrow \ldots \rightarrow \alpha _{k}\ldots \alpha _{1}$.

Suponiendo que la cadena de alfas final sea anulable, eso significa que cada uno de los $A_{i}$ y $\alpha _{i}$ también lo son (notar que más arriba habíamos llegado a que también los $A_{i}'$ y $\alpha _{i}'$ eran anulables, esto es, los que derivaban en beta). Por lo tanto, los símbolos directrices de la producción (1) también incluirán a los siguientes de $A_{i-1}$. Como siguientes de $A_{i-1}$ es un conjunto no vacío por la propiedad anterior, la intersección de los directrices de ambas producciones también será no vacía, con lo que G debe ser no LL(1) (nuevamente absurdo).

La última posibilidad es que la cadena de alfas sea no anulable, es decir, existe algún terminal a en primeros de dicha cadena. Con lo cual, ese valor a está presente en los directrices de la producción (1). Pero como los $\alpha _{j}'$, j < i, son anulables, entonces puedo llegar a que $A\alpha _{k}\rightarrow ^{*}A_{i-1}'\alpha _{i-1}'\ldots \alpha _{1}'\alpha _{k}\ldots \alpha _{1}\rightarrow ^{*}A_{i-1}'\alpha _{k}\ldots \alpha _{1}\rightarrow ^{*}A_{i-1}'a\gamma$.

De eso se deduce que a queda en siguientes de $A_{i-1}$, que está incluido en los símbolos directrices de la producción (2). Entonces, a pertenece a los directrices de ambas producciones y se produce el conflicto para que G no sea LL(1).

Los lenguajes LL(1) estan contenidos de manera propia en los lenguajes libres de contexto determinísticos.

Eliminacion de recursividad a izquierda

Es posible eliminar la recursividad a izquierda de una gramática mediante un algoritmo. Para eliminar la recursividad a izquierda directa de A, por ejemplo,

$A\rightarrow A\alpha _{1}|\ldots |A\alpha _{m}|\beta _{1}|\ldots |\beta _{n}$

Se genera un nuevo símbolo A' y se redefine A tal que

$A\rightarrow \beta _{1}A\prime |\ldots |\beta _{n}A\prime$
$A\prime \rightarrow \alpha _{1}A\prime |\ldots |\alpha _{m}A\prime |\lambda$

A su vez, para eliminar recursividad a izquierda en general (es decir, también la indirecta) se usa el siguiente algoritmo:

Numerar los no terminales de 1 a N

Para i = 1 to N
  Para j = 1 to i-1
     Sustituir cada Ai -> Aj γ por
     Ai -> δ1 γ | δ2 γ | ... | δk γ
     donde Aj -> δ1 | δ2 | ... | δk

     Eliminar recursividad a izquierda directa de cada Ai

La idea del algoritmo es recorrer cada una de los no terminales y eliminar todas las producciones que tengan como primer símbolo generado algún no terminal anterior, cambiandolas por una producción equivalente que no depende de ese no terminal. Esto solamente puede generar recursividad a izquierda directa, que se elimina con el método anterior.

Al finalizar, cada no terminal podrá derivar en una cadena que tenga, como primer elemento, solamente un terminal o un no terminal de numeración mayor.

Factorizacion

Dada una producción de la forma $A\rightarrow \alpha \beta _{1}|\alpha \beta _{2}$, siendo alfa el prefijo común de mayor longitud entre ambas cadenas, se puede factorizar usando:

$A\rightarrow \alpha A'$
$A'\rightarrow \beta _{1}|\beta _{2}$

Notar que a pesar de los algoritmos para eliminar factorización y recursividad a izquierda, puede haber lenguajes para los que no haya una gramática LL(1) que los reconozca (por ejemplo, cualquier lenguaje libre de contexto no determinístico, como ser $ww^{r}$).

ASDP Recursivo

Un analizador sintáctico descendente predictivo puede implementarse de manera recursiva definiendo un procedimiento para cada uno de los símbolos no terminales presentes en la gramática. Cada procedimiento contiene un switch dependiendo en el valor del token actual. Si el token pertenece al conjunto de símbolos directrices de una producción del no terminal del procedimiento, entonces se "ejecuta" la producción actual: los terminales son consumidos de la entrada y para los no terminales se ejecuta su procedimiento correspondiente. Por ejemplo:

Producciones
T -> A
T -> ^A;
A -> i | c | n

Proc A()
  if (token in {i,c,n})
     A()
  else if (token in {^})
     match(^)
     A()
     match(;)
  else
     error()

La mayor desventaja es que implica generar código nuevo para cada gramática, además de ser recursivo lo que generalmente es menos performante. La ventaja es que es menos restrictivo: en principio puede capturar cualquier lenguaje libre de contexto no recursivo a izquierda.

ASDP con Tabla

(Ver definición de la práctica).

El analizador sintáctico descendente predictivo puede implementarse también usando una tabla. La ventaja es que el código es siempre el mismo, sólo varía la tabla que se usa; además de ser más rapido pues no es recursivo. Se construye a partir de la gramática extendida.

La tabla es una matriz M con tantas columnas como símbolos terminales y tantas filas como no terminales, tal que $M(a,A)='A\rightarrow \alpha '$ sii $a\in SD(A\rightarrow \alpha )$.

El algoritmo, dada la cadena de entrada w, el token actual t y un stack auxiliar, es el siguiente. Recordar que el lado derecho de la producción Y1Y2 ... Yk se apila al revés de manera que el primer símbolo quede como tope.

Repetir
  Si tope in Vt
      Si tope === t
         extraigo tope de la pila
         avanzo 1 en w
      Si no
         error
  Si no
      Si M(t, tope) === (tope --> Y1Y2 ... Yk)
         extraigo tope de la pila
         apilo YkYk-1 ... Y1 
      Si no
         error
Hasta que tope === # && t === #

Gramática LL(k)

Una gramática LL(k) es análoga a una LL(1). La única diferencia radica en que los conjuntos de primeros y siguientes, en lugar de contener terminales, contienen cadenas de terminales de longitud a lo sumo k. Esto reduce las colisiones entre los símbolos directrices de producciones para el mismo no terminal, pero aumenta significativamente el tamaño de la tabla de parseo en memoria.

Decidibilidad

• Dado un k y una gramática G, es G LL(k)? Es decidible, se construye el analizador y se evalúa si se producen conflictos.
• Dada una gramática G, existe un k tal que G sea LL(k)) No es decidible.
• Dada una gramática G no LL(1), existe una gramática G' LL(1) tal que represente el mismo lenguaje? No es decidible.

Analizadores Sintácticos Ascendentes

Un estilo de análisis sintáctico de abajo hacia arriba es conocido como "shift-reduce parsing". Shift-Reduce intenta construir un árbol de parseo para una cadena de entrada empezando en las hojas y trabajando hacia arriba en dirección a la raiz. Es como el proceso de reducir un string w al símbolo distinguido inicial de la gramática. En cada reducción un substring particular de w que coincide con el lado derecho de una producción se reemplaza por el no terminal de la izq. de la misma, y si el substring se elige correctamente en cada paso, se reconstruye en reversa una derivación más a la derecha.

Definicion: Pivote: Dada $G=<V_{N},V_{T},P,S>$ y una forma sentencial derecha $\alpha \rho \beta$: $\rho$ es pivote si y sólo si $\exists \ (N\rightarrow \rho )\wedge \ S\rightarrow _{D}^{*}\ \alpha N\beta \ \rightarrow _{D}\ \alpha \rho \beta$

Informalmente el pivote es una subcadena que matchea con el lado deerecho de una producción y cuya reducción representa un paso "en reversa" de la derivación más a la derecha de la cadena. Es importante notar que en muchos casos el substring $\beta$ más a la derecha que matchea con alguna producción no es un pivote, ya que una reducción de $\beta$ llevaría a una cadena que no se puede seguir reduciendo al símbolo distinguido. Si la gramática no es ambigua, existe un único pivote en una forma sentencial derecha.

Algoritmo: Shift reduce (algoritmo general)

Sea w = a1 ... an la cadena de entrada
pc el símbolo apuntado en w
La pila inicializada en vacio, tope es el tope de la pila

elFin := F
error := F
Repetir hasta elFin
     Según
         tope es pivote
             Desapilar pivote
             Apilar A donde (A->tope) es una prod. de G
         pila == S y fin de w
             aceptar w
             elFin := T
         no es fin de w
             apilar pc
             Si pc != a_n
                 pc++
                 desplazar
         otro caso
             error := T
             elFin := T

Precedencia Simple

Definicion: Relaciones de precedencia de Wirth-Weber. Permiten definir el pivote dada una forma sentencial derecha; el mismo queda encerrado entre <> al evaluar todas las relaciones de precedencia entre símbolos consecutivos. Notar que no son relaciones de equivalencia u orden.

Sea $G=<V_{T},V_{N},P,S>$, y $\alpha$ una forma sentencial derecha tal que $\alpha =...XY...$,

• ${\dot {=}}:V\times V$
  • $X{\dot {=}}Y\Leftrightarrow (A\to \alpha XY\beta )\in P$
  • Implica que tanto X como Y están en el pivote de $\alpha$.

• ${\dot {<}}:V\times V$
  • $X{\dot {<}}Y\Leftrightarrow (A\rightarrow \alpha XB\beta )\in P\ \wedge \ (B\rightarrow ^{+}Y\gamma )$
  • Implica que Y está en el pivote de $\alpha$ y X no.

• ${\dot {>}}:V\times V_{T}$
  • $X{\dot {>}}a\Leftrightarrow (A\to \alpha BY\beta )\in P\ \wedge \ (B\rightarrow ^{+}\gamma X)\ \wedge \ (Y\rightarrow ^{*}a\delta )$
  • Implica que X está en el pivote de $\alpha$ y Y no, notar que Y debe ser un terminal pues alfa es una forma sentencial derecha, esto es, no puede haber no terminales no expandidos a la derecha del pivote.

Gramática de Precedencia Simple

Definicion: Gramatica propia

• Si no hay símbolos inútiles (símbolos inalcanzables o inactivos)
• Si no hay producciones $\lambda$ excepto $S\rightarrow \lambda$ (y S no aparece en la parte derecha de ninguna producción)

Definicion: Gramaticas de precedencia

• Si es propia y $\forall A,B\in V$ en $G$, a lo sumo sostienen una relación de precedencia; es decir, no hay conflictos.

Definicion: Una gramatica es de precedencia simple si:

• Es de precedencia y unívocamente inversible (no hay dos lados derechos iguales) [Si $(A\rightarrow \alpha ),(B\rightarrow \beta )\in P\Rightarrow ((\alpha =\beta )\rightarrow (A=B))$]

Algoritmo de Parseo por Precedencia Simple

Completar tabla de PS

Puede hacerse algorítmicamente utilizando las definiciones de P+, U+ y P*, o calculando las relaciones de precedencia entre símbolos consecutivos de la gramática "a ojo".

$P^{+}(X)=\{Y\in V\;/\;X\rightarrow ^{+}Y\alpha \}$
$U^{+}(X)=\{Y\in V\;/\;X\rightarrow ^{+}\alpha Y\}$
$P^{*}(X)=\{P^{+}(X)\cup \{X\}\}\cap V_{T}$

para cada produccion A -> alfa
   para cada XY in subCadenas(alfa)
      definir X = Y
   IF Y in VN 
      definir X < P+(Y)
   IF X in VN
      definir U+(X) > P*(Y)

para cada X in VN Union VT
   definir # < S Union P+(S)
   definir S Union U+(S) > #

Algoritmo de parsing

Tabla de precedencia sin conflictos y w cadena de entrada. (TC es donde apunta en w).

apilar #
repetir
   IF TOPE < TC o TOPE = TC
        apilar TC
        avanzar w
   ELSE
        IF TOPE > TC
           OBTENER alfa pivote en la pila
           BUSCAR la produccion A -> alfa
           IF no encuentra produccion A -> alfa 
                ERROR
           ELSE  
                reemplazar alfa en la pila por A
        ELSE
           ERROR
hasta TC = # y en la pila hay #S
Aceptar w

Analizador LR

Definiciones

Prefijo viable: Sea $\alpha \rho \beta$ una fsd (forma sentencial derecha) donde $\rho$ es pivote, $\gamma$ es prefijo viable si es prefijo de $\alpha \rho$. Son los prefijos de una fsd que pueden aparecer en el stack de un parser shift-reduce. Intuitivamente, son los prefijos de cualquier cadena que termine en el pivote. Vale que el conjunto de los prefijos viables de un lenguaje libre de contexto genera un lenguaje regular.

Item: Un item LR(0) de una gramática G es una producción de G con un punto en alguna posición del lado derecho (definición del dragón). Notar que el conjunto de items de una gramática es finito.

Item válido: Dado un prefijo viable $\gamma =\delta \alpha$, $[A\rightarrow \alpha .\beta ]$ es un ítem válido para $\gamma$ ssi $S\rightarrow _{D}^{*}\ \delta Aw\ \rightarrow _{D}\ \delta \alpha \beta w$, con $(A\rightarrow \alpha \beta )\in P$. Notar que acá $\alpha \beta$ es un pivote.

En general un item puede ser válido para muchos prefijos viables. El hecho de que un item sea válido para $\delta \alpha$ da mucha información acerca de si conviene hacer un shift o un reduce teniendo $\delta \alpha$ en el stack. Si $\beta$ no es vacío, nos dice que todavía no leimos y escribimos todo el pivote en el stack, por lo que hay que hacer shift. Si $\beta$ fuera nulo, nos diría que $A\rightarrow \alpha$ es el pivote y que habría que reducir por esa producción. Lo que es cierto es que dos items válidos puede sugerir acciones distintas, con lo cual surgen conflictos. Algunos de estos conflictos se pueden solucionar mirando a los próximos símbolos en el input, pero no todos se van a poder solucionar para un gramática arbitraria.

Item completo: Es un item que el punto lo tiene al final de la parte derecha de la producción.

Construccion del Automata

La idea principal es que el conjunto de los prefijos viables de un (¿lenguaje libre de contexto o LR?) es regular. Entonces existe un AFND-L cuyo lenguaje son ellos. Sea $M=<K,(V_{N}\cup V_{T}),\delta ,q_{0},K>$ con $K=\{i\ |\ i\ {\textrm {es\ item\ en\ }}G\}\cup \{q_{0}\}$. Todos los estados van a ser finales.

Definimos $\delta$ de la siguiente forma:

1. $\delta (q_{0},\lambda )=\{[S\rightarrow .\alpha ]\ |\ S\rightarrow \alpha \in P\}$
2. $\delta ([A\rightarrow \alpha .B\beta ],\lambda )=\{[B\rightarrow .\gamma ]\ |\ B\rightarrow \gamma \in P\}$, $B\in V_{N}$
3. $\delta ([A\rightarrow \alpha .X\beta ],X)=\{[A\rightarrow \alpha X.\beta ]\}$

Teorema: Dadas $G=<V_{T},V_{N},P,S>$ GLC y M el AFND-L construido, se cumple que $A\rightarrow \alpha .\beta \in \delta (q_{0},\gamma )\Leftrightarrow$ $A\rightarrow \alpha .\beta$ es item válido para $\gamma$ prefijo viable. Idea de la demostración:

• Ida (=>): Se prueba por Inducción en la longitud del camino para consumir $\gamma$.
  • El caso base es long=1, con lo cual la única transición posible $\lambda$ (por 1) y $\gamma$ tiene que ser la cadena vacía. Como $\delta (q_{0},\gamma )=\delta (q_{0},\lambda )$ y $S\rightarrow .\alpha \in \delta (q_{0},\lambda )$ y es además un item válido para el prefijo viable $\gamma =\lambda$, el caso base se cumple.
  • Para el paso inductivo asumimos verdadera la HI para long de camino menores a $k$. Las reglas para las transiciones 2) y 3) implican dos formas posibles para la última transición en el camino. Nuestra hipótesis es $[A\rightarrow \alpha .\beta ]\in \delta (q_{0},\gamma )$ en $k$ transiciones:
    1. Está etiquetada con $X\in V$: Por hipótesis y como además sabemos que en la última transición consumimos $X$, si tomamos $\alpha =\alpha 'X$ y $\gamma =\gamma 'X$, el estado anterior tienen que ser $[A\rightarrow \alpha '.X\beta ]$, al que se llegó de $q_{0}$ por $\gamma '$ en $k-1$ pasos, es decir, $[A\rightarrow \alpha '.X\beta ]\in \delta (q_{0},\gamma ')$. Pero al ser $k-1$ transiciones, vale la hipótesis inductiva, o sea, vale que $[A\rightarrow \alpha '.X\beta ]$ es un item válido para el prefijo viable $\gamma '$. Qué significa esto? Que $\alpha 'X\beta$ es un pivote, también que $\gamma '=\delta \alpha '$ y que $S\rightarrow _{D}^{*}\ \delta Aw\ \rightarrow _{D}\ \delta \alpha 'X\beta w$ (todo por la definición de prefijo viable e item válido para el mismo). Pero entonces notemos que $\delta \alpha 'X=\gamma$ también cumple la definición de prefijo viable (por quién es el pivote) y que $[A\rightarrow \alpha 'X.\beta ]$ es un item válido para $\gamma$. Como $[A\rightarrow \alpha 'X.\beta ]=[A\rightarrow \alpha .\beta ]$, llegamos a lo que queríamos: $[A\rightarrow \alpha .\beta ]\in \delta (q_{0},\gamma )$ implica $[A\rightarrow \alpha .\beta ]$ es un item válido para $\gamma$ prefijo viable.
    2. Está etiquetada con $\lambda$: Como la última transición fue $\lambda$ tiene que haber sido usando la definición 2 de $\delta$. Primero, esto implica que para que el item tenga la forma $[B\rightarrow .\gamma ]$ debe pasar que $\alpha =\lambda$. Segundo, el estado previo tiene que haber sido de la forma $[B\rightarrow \alpha _{1}.A\beta _{1}]$, y a él se tiene que haber llegado del estado inicial por el mismo $\gamma$ (ya que no se consumió entrada), o sea, tiene que pertenecer a $\delta (q_{0},\gamma )$. Nuevamente vale la hipótesis inductiva, entonces podemos deducir que $[B\rightarrow \alpha _{1}.A\beta _{1}]$ es item válido del prefijo viable $\gamma$. O sea, $S\rightarrow _{D}^{*}\ \delta Bw\ \rightarrow _{D}\ \delta \alpha _{1}A\beta _{1}w\ \rightarrow _{D}\ \delta \alpha _{1}\beta \beta _{1}w$ (el último paso por hipótesis y porque concluimos que $\alpha =\lambda$). Pero entonces $\gamma =\delta \alpha _{1}$ es también prefijo viable para el pivote $\beta$, para el cual $[A\rightarrow \ .\beta ]$ es un item válido, llegando así a lo que queríamos probar.
• Vuelta (<=)
  • Probamos primero el Lema: Si $[A\rightarrow .\alpha ]$ es item válido para $\gamma$ prefijo viable, entonces $[A\rightarrow .\alpha ]\in \delta (q_{0},\gamma )$. Demostración por inducción sobre $i$ en $S\rightarrow _{D}^{i}\ \gamma Aw\ \rightarrow _{D}\ \gamma \alpha w$ (esto es aplicar las definiciones de p.v. e i.v. ).
    • Caso base i = 0: Debe pasar que $S\rightarrow \gamma \alpha w=\alpha \ \ (\gamma ,w=\lambda )$. En este caso el item es en realidad $S\rightarrow .\alpha$ y $\gamma =\lambda$. Por construcción de $\delta$ sabemos que $[S\rightarrow .\alpha ]\in \delta (q_{0},\lambda )$.
    • Paso inductivo: (supongamos HI cierta para $i$). Por hipotesis del lemma y def. de p.v. e i.v., $S\rightarrow _{D}^{i+1}\ \gamma Aw\ \rightarrow _{D}\ \gamma \alpha w$ . Como el $A$ tiene que haber surgido en alguna derivación anterior o igual a $i+1$, $S\rightarrow _{D}^{k}\ \gamma 'Bw'\rightarrow _{D}\ \gamma '\gamma ''Aw''w'\ \rightarrow _{D}^{i-k}\ \gamma Aw$ . Notar que $\gamma '\gamma ''=\gamma$ ya que ningún no terminal a la derecha de $A$ puede expandirse antes que esta (por ser derivación más a la derecha). Ahora, como $\gamma '\gamma ''Aw''w'$ es una f.s.d, $[B\rightarrow .\gamma ''Aw'']$ es un ítem válido para el prefijo viable $\gamma '$. Por H.I., entonces $[B\rightarrow .\gamma ''Aw'']\in \delta (q_{0},\gamma ')$. Pero aplicando la definición (3) de $\delta$ por cada símbolo de $\gamma '$ se ve que podemos llegar del estado $[B\rightarrow .\gamma ''Aw'']$ a $[B\rightarrow \gamma ''.Aw'']$ consumiendo $\gamma ''$. Entonces, $[B\rightarrow \gamma ''.Aw'']\in \delta (q_{0},\gamma '\gamma '')=\delta (q_{0},\gamma )$ . Para terminar, por la def. (2), $[A\rightarrow .\alpha ]\in \delta (\delta (q_{0},\gamma ),\lambda )=\delta (q_{0},\gamma )$, como queríamos probar.
  • Ahora, con el lema probado si $[A\rightarrow \alpha .\beta ]$ es item válido para $\gamma$, entonces debe pasar que $[A\rightarrow .\alpha \beta ]$ es item válido para $\delta '$ prefijo viable (con $\gamma =\delta '\alpha$)- Por el lema anterior , $[A\rightarrow .\alpha \beta ]\in \delta (q_{0},\delta ')\Rightarrow$ (usando la definición 3 de $\delta$) $[A\rightarrow \alpha .\beta ]\in \delta (q_{0},\delta '\alpha )=\delta (q_{0},\gamma )$

Construccion de conjuntos de items

Funcion Clausura

Closure encuentra todos los items en el mismo estado.

closure(I):

1. Todo item en I es también un item en closure(I)
2. Si $[A\rightarrow \alpha .B\beta ]$ está en closure(I) y $[B\rightarrow .\gamma ]$ es un item, entonces agregamos $[B\rightarrow .\gamma ]$ a closure(I)
3. Repetimos hasta que no se pueden agregar más items a closure(I)

Funcion Goto

Goto encuentra el nuevo estado después de consumir un símbolo de la gramática mientras estamos en el estado actual.

goto(I, X): closure( { $A\rightarrow \alpha X.\beta |A\rightarrow \alpha .X\beta \in I$ } )

donde I es un conjunto de items y X es un símbolo de la gramática.

Procedimiento para conjuntos de items

$q_{0}$ <- clausura( { $s'\rightarrow s\$$ } )
K <- {$q_{0}$} sin marcar
mientras hay I $\in$ sin marcar
   marcar I
   para cada x $\in$ V
      j <-- goto[i,x]
      si j $\notin$ K entonces agregar j a K sin marcar

Algoritmo de parseo LR

Todos los analizadores LR se comportan de la misma forma, lo que cambia es la construcción de la tabla de parsing y/o el autómata, que son específicos a cada clase.

Entrada. Una cadena w y una tabla de parsing LR con funciones acción y goto para una gramática G.

Salida. Si w pertenece a L(G), un parseo ascendente de w; si no, error.

Método. Inicialmente, el parser tiene $s_{0}$ en el stack, donde $s_{0}$ es el estado inicial, y w$ en el buffer the entrada. El parser ejecuta el siguiente algoritmo hasta que acepta la cadena o encuentra en la tabla una entrada de error.

apuntar ip al primer símbolo de w$
repetir siempre 
  sea s el estado en el tope de la pila y 
      a el símbolo apuntado por ip
  si action[s, a] = shift s' entonces
      apilar a y luego s'
      avanzar ip
  si no, si action[s, a] = reducir A -> beta
      desapilar 2 * |beta| símbolos
      sea s' el nuevo estado en el tope de la pila
      apilar A y luego goto[s', A]
      imprimir A -> beta
  si no, si action[s, a] = aceptar
      terminar
  si no
      error       

Analizador LR(0)

Un analizador LR(0) parsea una cadena utilizando el algoritmo anteriormente mencionado y una tabla. Las tablas de parseo tienen las mismas filas y columnas para todos los analizadores, en las filas ponemos todos los estados que obtuvimos del autómata y en las columnas todos los terminales y no terminales.

Algoritmo para crear una tabla de parseo LR(0):

 Para cada estado
     1. Transición a otro estado usando un símbolo terminal
        es un shift a ese estado $(shift\;to\;s_{n})$
     2. Transición a otro estado usando un no-terminal
        es un goto a ese estado $(goto\;s_{n})$
     3. Si hay un ítem $[A\rightarrow \alpha .]$ en el estado
        hacemos una reducción con esa producción para todos los terminales
        ($reduce\;k$, donde k es la k-ésima producción)

Analizador SLR

El problema de los analizadores LR(0) es que hay muchos conflictos shift/reduce ya que al reducir lo hacemos sea cual sea el siguiente caracter. Los analizadores SLR, mejoran este aspecto mirando el siguiente token y reduciendo solo sí el mismo se encuentra dentro de los siguientes del no terminal a la izquierda de la producción del ítem. El algoritmo para crear la tabla de parseo es idéntico al LR(0) excepto en el tercer paso:

 3. Si hay un ítem $[A\rightarrow \alpha .]$  en el estado,
    para todos los terminales $c\in follow(A)$ hacer una
    reducción con la producción $(reduce\;k)$

Analizador LR(1)

Necesitamos definir nuevas funciones Closure y Goto para crear un analizador LR(1).

 Closure(I):
   repetir
     para todos los ítems $[A\rightarrow \alpha .X\beta \;\;c]$ en I
       para cualquier producción $X\to \gamma$
         para cualquier $d\in first(\beta c)$ 
           $I=I\cup {[X\to .\gamma \;\;d]}$
   hasta que I no cambie
 retornar I

 Goto(I, X):
   J = {}
   para todos los ítems $[A\rightarrow \alpha .X\beta \;\;c]$ en I
   $J=J\cup {[A\to \alpha X.\beta \;\;c]}$

Nuevamente la construcción de la tabla de parseo es idéntica salvo en el último paso:

 3. Si hay un ítem $[A\to \alpha .\;\;a]$  en el estado, hacemos una
    reducción para el símbolo de entrada "a" con la producción $(reduce\;k)$

Los parsers LR(1) reducen los conflictos reduce/reduce que eran más frecuentes en los parsers SLR.

Analizador LALR

Los analizadores LR(1) tienen un gran número de estados, lo que los hace poco eficientes. La idea de los analizadores LALR es: si dos estados son idénticos, excepto por el símbolo de look ahead de los ítems, los colapsamos en uno solo.

Esta forma de colapsar estados no puede producir un conflicto shift/reduce que no estuviera presente en el autómata LR(1), dado que las acciones the shift no dependen del lookahead, si no tan sólo del core del item. Sin embargo, sí puede generar conflictos reduce/reduce, como mostramos en el siguiente ejemplo:

S' -> S
S  -> aAd | bBd | aBe | bAe
A  -> c
B  -> c

Que genera el lenguaje {acd, ace, bcd, bce}. Esta gramática es LR(1). Si construímos el autómata LR(1), obtenemos el conjunto de items {$[A\rightarrow c.,d],[B\rightarrow c.,e]$} para el prefijo ac y {$[A\rightarrow c.,e],[B\rightarrow c.,d]$} para bc. Si los unimos:

A -> c., d/e
B -> c., d/e

Vemos que introdujimos un conflicto reduce/reduce, dado que tanto $[A\rightarrow c]$ como $[B\rightarrow c]$ pueden ser utilizadas para reducir para los caracteres d y e.

Propiedades LR

Propiedad: Si L es LLCD (Lenguaje Libre de Contexto Determinístico) y libre de prefijos, entonces existe una gramatica LR(0) que lo captura.

Propiedad: Para todo lenguaje LLCD existe una gramatica LR(k) que lo representa.

Propiedad: Para toda gramatica LR(k) existe una LR(1) equivalente.

Propiedad: Toda gramática analizable con un parser predictivo descendente es analizable con un LR(1).

Compiladores

La parte de compiladores se encuentra fuertemente vinculada con el uso de gramáticas de atributos, DDS y TDS, depende de ésta para realizar los análisis y generación de código.

Los pasos que realiza el compilador son los siguientes, partiendo del programa fuente:

• Análisis lexicografico (genera cadena de tokens)
• Análisis sintáctico (parseo, genera árbol de derivación)
• Análisis estático (genera árbol decorado usando DDS)
• Generación de código intermedio (con DDS, optimizaciones generales)
• Generación de código objeto (con DDS, optimizaciones específicas según arquitectura)

Análisis estático

El análisis estático se realiza sobre el árbol de derivación del programa generado tras el parseo, e incluye los siguientes items:

• Chequeo de tipos
• Chequeo de flujo del programa (break, continue, etc)
• Chequeo de unicidad (ej en switches)
• Apareamiento de etiquetas (linking)

Chequeo de Tipos

El chequeo de tipos se hace manteniendo una tabla global de tipos que relaciona una variable con un tipo de datos. Luego a medida que se va parseando el programa se verifican los tipos correctos de las expresiones usando dicha tabla.

Expresión de Tipo: Una expresión de tipo es un tipo básico o el resultado de aplicar un constructor de tipo a una expresión de tipo.

Tipos básicos: Los tipos básicos del lenguaje, deben incluir a los tipos vacío y error_tipo.

Constructores de tipo: Arreglos, registros (conjuntos de tuplas nombre:tipo), punteros y funciones.

Sistema de tipos: Conjunto de reglas que permiten asignar expresiones de tipo a fragmentos del programa.

Sistema de tipos seguro: Un sistema de tipos es seguro cuando el chequeo de tipos estático (en tiempo de compilacion) asegura que no surjan errores de tipo en runtime.

Lenguaje fuertemente tipado: Lenguaje que cuenta con un sistema de tipos seguro. Notar que las excepciones de tipo InvalidCast no cuentan como errores de tipo.

Equivalencia de tipos: La equivalencia de tipos puede definirse por nombre o por estructura. La equivalencia por estructura consiste en verificar si ambos son básicos y matchean sus tipos, o si el último constructor aplicado es el mismo y sus tipos contenidos matchean (ej puntero a int con puntero a int, primero se chequea puntero y luego int). La equivalencia por nombre es por strings.

Sobrecarga de operadores

La sobrecarga de operadores permite que un mismo operador pueda tomar distintos tipos como operandos y devolver un tipo distinto según estos últimos. Tomemos por ejemplo el operador suma, y los tipos básicos int y float.

Si se efectúa una suma entre dos enteros, el resultado de esa expresión será también un int. Ahora bien, si se realiza una suma entre dos float, el resultado también será float. Por lo tanto, dada una producción del tipo:

E1 -> E2 + E3

el atributo sintetizado tipo de E1 dependerá de los tipos de E2 y E3:

E1.tipo <- if (E2.tipo = int && E3.tipo = int) int
           else if (E2.tipo = float && E3.tipo = float) float
           else if (E2.tipo = int && E3.tipo = float) float
           ...
           else error_tipo

Notar que si E2 es de tipo int y E3 de tipo float, se aplica la suma de floats. Para esto se debe coercionar de manera implítica el tipo de E2 a float. En otras palabras, se hace un casteo implícito.

Generación de código intermedio

La generación de código intermedio involucra el uso de alguna de las siguientes estructuras de representación para las expresiones:

• Árboles sintácticos: Tienen como nodos intermedios los operadores, y los hijos de cada nodo son las subexpresiones que actúan de operandos. Las hojas son las variables. No confundir con árboles de análisis sintáctico, que son los generados por el parser.
• Grafos dirigidos acíclicos: Similares a los anteriores, pero pueden tener ciclos no dirigidos (no ciclos dirigidos) para reutilizar subexpresiones y no generarlas más veces que las necesarias.
• Notación postfija: La notación postfija emula un lenguaje de pila, y es no ambigua y fácil de manejar. Ejemplo, a+b*c se traduce a abc*+.

Código de tres direcciones

El código de tres direcciones es un tipo de código intermedio que se puede utilizar donde cada instrucción consiste en una asignación de una operación de dos operandos, así como estructuras de control.

• Expresiones binarias: X = Y op Z
• Expresiones unarias: X = op Z
• Asignaciones: X = Z
• Saltos: goto E (donde E es una etiqueta)
• Saltos condicionales: E Y op Z (si Y op Z entonces goto E)
• Calls: x1 param; x2 param; ... xn param; n call p (call a P con n parametros)
• Indexacion: X = Y[i]
• Referencias: X = &Y