Tabla de Contenidos:

Alfabeto T

· |T| < w

Definición intuitiva de T*

T* es una estructura algebraica con la particularidad de ser un monoide (semigrupo con identidad); para ello se debe
cumplir con la propiedad de asociatividad y contener además al elemento identidad.

Por lo tanto, sea T* = (T, · , e ) y supongamos que x,y,z Î T entonces se cumple que:

(x · y) · z = x · (y · z) (Asociatividad)

x · e = e · x = x (Elemento Identidad)

T* se define como el conjunto de todas las secuencias finitas de elementos de T.

Operaciones sobre T*

            · Concatenación ( yuxtaposición ):
                  conc: T* x T* ® T*
                  conc( x , y ) = x · y = xy

            · Longitud:
                  long: T* ® Nat
                  long: cantidad de símbolos que tiene un elemento de T*

· La cadena nula se define como:
long ( e ) = 0, ( " x ) ( x Î T* => x · e = e · x = x)

Definición Precisa de T*

        1. e Î T*
        2. t Î T Ù y Î T* ® ty Î T*
        3. Todo elemento de T* se construye a partir de la aplicación finita de 1 y 2.

· Ejemplo: long ( ty ) = 1 + long ( y )

Definición del lenguaje L sobre un alfabeto T

· L Í T*

Operaciones Sobre L

· L1 + L2 = L1 È L2 = { x | x Î T* Ù ( x Î L1 Ú x Î L2) }

· L1 · L2 = { x·y | (x Î L1 Ù y Î L2) }

· Lº = { e }

Expresiones Regulares

        1. Æ   denota al lenguaje L = Æ
        2. e denota al lenguaje L = { e }
        3. " t Î T, t denota al lenguaje L = { t }
        4. Si P y Q denotan los lenguajes Lp y Lq respectivamente, entonces:
           · ( P + Q ) denota al lenguaje Lp + Lq
          · ( P · Q ) denota al lenguaje Lp · Lq
           · ( P )* denota al lenguaje Lp*
        5. Toda expresión regular se construye a partir de la aplicación finita de 1 a 4.

Axiomas sobre Expresiones regulares (ER)

" a, b, g Î E.R.

          · ( a + b ) + g = a + ( b + g )
          · ( a · b ) · g = a · ( b · g )
          · a · ( b + g ) = ( a · b ) + ( a · g )
          · ( a + b ) · g = ( a · g ) + ( b · g )
          · a + b = b + a
          · a + a = a
          · Æ + a = a + Æ = a
          · Æ · a = a · Æ = Æ
          · e · a = a · e = a
          · e + ( a · a* ) = a*
          · ( e + a )* = a*

· llamaremos a+ = a · a*

Grafo Asociado a una Expresión Regular

Representación del Grafo Asociado a una Expresión Regular como un Autómata

Finito no determinístico (AFND)

        · Un AFN se define como A = (Q,T,d,S,F) donde:
             o Q es el conjunto Finito de Estados
             o T es el Alfabeto
             o S Î Q, S es el Estado Inicial
             o F Í Q, Q es el conjunto de Estados Finales
             o d Es el conjunto finito de Transiciones entre Estados
                d: Q ´ (T È { e }) ® Ã(Q)

        · Ejemplo: AFND = (Q,T,d,S,F) donde:
             o Q = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14}
             o T = { a , b }
             o S = 1
             o F = { 14 }
             o d = { < 1, e , 2 >, < 1, e , 12 >, < 2, e , 3 >, < 2, e , 9 >, < 3, e , 4 >, < 3, e , 5 >, < 4, a,6 >, < 5, b , 7 >,
                   < 6, e , 8 >, < 7, e , 8 >, < 8, e , 3 >, < 8, e , 9 >, < 9, e ,10 >, < 10, a,11 >, < 11, e ,14 >, < 13, e ,14> }

Observación:

La cadena de caracteres "aba"

Se reconoce a la cadena "aba" ya que el conjunto de estados intersectados con el conjunto de estados finales
es diferente al vacío. Nótese que para "ab" no sucede.

Función de Reconocimiento de un AFND

: Ã (Q) x T* ®Ã(Q)

(Q,w) = Æ                                            ( I )
(P, e) = P                                             ( II )
(P, t.w) = (d´´(P,t), w)                      ( III )

        donde
           d´´: Ã(Q) ´ T ® Ã(Q)
           d´´: (Q,w) = Æ                            ( IV )
           d´´(P,t) = e ´(d´(P,t))                     ( V )

            donde
              d´: Ã (Q) ´ T ® Ã (Q)
              d´(Æ,t) = Æ                            ( VI )
              d´(P,t) = Èd(q,t)                    ( VII )
                            q Î p

           y
            e´: Ã(Q) ® Ã(Q)
            e´(P) = È e( q )                     ( VIII )
                        q Î p

         donde:
           e: Q ® Ã(Q)
             se define como:

t Î e( t )
x Î e( t ) Ù z Î d( x, e ) ® z Î e( t )

tendremos que:
x Î L Û ( e( S ), x ) Ç F ¹ Æ

Esta última fórmula se determina rápidamente por medio del teorema de inducción:

- Cláusula base: Si es cierta la formulación anterior debe cumplirse tanto para el lenguaje vacío como con los
elementos "t" y "e"

L = Æ

(" x) x Î L Û ( e( S ), x ) Ç F ¹ Æ, partiendo de la fórmula original se tiene que:
(" x) L = Æ Û ( e( S ), x ) Ç F = Æ

S = 1 y F = { 2 }

Ahora, se sabe que el dominio de : Ã(Q) x T* ®Ã(Q), por lo que x Î T*.
Y si x Î T*, entonces "x" puede ser e ó de la forma yt.

                            Para x = e
                                (" x) L = Æ Û ( e( S ), x ) Ç F = Æ    (Sustituyendo el valor de x en la fórmula)
                                (" x) L = Æ Û ( e( S ), e ) Ç F = Æ   (Aplicando la fórmula II)
                                (" x) L = Æ Û e( S ) Ç F = Æ                (Sustituyendo el valor de S y F)
                                (" x) L = Æ Û e( 1 ) Ç { 2 } = Æ           (Viendo el autómata obtenemos la clausura)
                                (" x) L = Æ Û { 1 } Ç { 2 } = Æ           (Aplicando la intersección de los dos elementos)
                                (" x) L = Æ Û Æ

                            Para x = yt
                                (" x) L = Æ Û ( e( S ), x ) Ç F = Æ    (Sustituyendo el valor de x en la fórmula)
                                (" x) L = Æ Û ( e( S ), yt ) Ç F = Æ
                                Debido a que yt Î T*, vemos el autómata y se sabe que para "y" no esta definida, por lo tanto
                                ( e( S ), yt ) = Æ
                                (" x) L = Æ Û Æ Ç F = Æ                    (Aplicando la intersección de los dos elementos)
                                (" x) L = Æ Û Æ

Con ello podemos argumentar que para todo x ÎL, si ese lenguaje L = Æ, pues tan solo el autómata podrá
reconocer a este mismo (elemento vacío).

L = { e }

(" x) x Î L Û ( e( S ), x ) Ç F ¹ Æ, partiendo de la fórmula original tenemos que:
(" x) L = { e } Û ( e( S ), x ) Ç F ¹ Æ

S = 1 y F = { 2 }

Ahora, se sabe que el dominio de : Ã(Q) x T* ®Ã(Q), por lo que x Î T*.
Y si x Î T*, entonces "x" puede ser e ó de la forma yt.

                            Para x = e
                                (" x) L = { e } Û ( e( S ), x ) Ç F ¹ Æ    (Sustituyendo el valor de x en la fórmula)
                                (" x) L = { e } Û ( e( S ), e ) Ç F ¹ Æ   (Aplicando la fórmula II)
                                (" x) L = { e } Û e( S ) Ç F ¹ Æ                (Sustituyendo el valor de S y F)
                                (" x) L = { e } Û e( 1 ) Ç { 2 } ¹ Æ           (Viendo el autómata obtenemos la clausura)
                                (" x) L = { e } Û { 2 } Ç { 2 } ¹ Æ           (Aplicando la intersección de los dos elementos)
                                (" x) L = { e } Û { 2 }¹ Æ

                            Para x = yt
                                (" x) L = { e } Û ( e( S ), x ) Ç F ¹ Æ    (Sustituyendo el valor de x en la fórmula)
                                (" x) L = { e } Û ( e( S ), yt ) Ç F ¹ Æ
                                Debido a que yt Î T*, vemos el autómata y sabemos que para "y" no esta definida, por lo tanto

                                ( e( S ), yt ) = Æ
                                (" x) L = { e } Û Æ Ç F ¹ Æ                    (Aplicando la intersección de los dos elementos)
                                (" x) L = { e } Û Æ

Con ello decimos que para cualquier x ÎL, si ese lenguaje L = { e }, pues no podrá reconocer a un string
de la forma yt sino unicamente reconocerá al epsilón.

L = { t }

(" x) x Î L Û ( e( S ), x ) Ç F ¹ Æ, partiendo de la fórmula original tenemos que:
(" x) L = { t } Û ( e( S ), x ) Ç F ¹ Æ

S = 1 y F = { 2 }

Ahora, sabemos que el dominio de : Ã(Q) x T* ®Ã(Q), por lo que x Î T*.
Y si x Î T*, entonces "x" puede ser e ó de la forma yw.

                            Para x = e
                                (" x) L = { t } Û ( e( S ), x ) Ç F ¹ Æ    (Sustituyendo el valor de x en la fórmula)
                                (" x) L = { t } Û ( e( S ), e ) Ç F ¹ Æ   (Aplicando la fórmula II)
                                (" x) L = { t } Û e( S ) Ç F ¹ Æ                (Sustituyendo el valor de S y F)
                                (" x) L = { t } Û e( 1 ) Ç { 2 } ¹ Æ           (Viendo el autómata se obtiene la clausura)
                                (" x) L = { t } Û { 1 } Ç { 2 } ¹ Æ           (Aplicando la intersección de los dos elementos)
                                (" x) L = { t } Û Æ

                            Para x = yw
                                (" x) L = { t } Û ( e( S ), x ) Ç F = Æ    (Sustituyendo el valor de x en la fórmula)
                                (" x) L = { t } Û ( e( S ), yw ) Ç F = Æ (Aplicando la fórmula III)
                                (" x) L = { t } Û (d´´( e( S ), y), w ) Ç F = Æ
                                Debido a que d´´ está definida en: Ã(Q) ´ T ® Ã(Q), entonces y Î T con w Î T*.
                                Por ende, viendo el autómata se tiene que los únicos valores que pueden tener "y" y "w" son: y=t, w=e
                                y para otro valor posible que pueda tener yw pues tan solo no será reconocido por el autómata.

Con ello podemos argumentar que para todo x ÎL, si ese lenguaje L = { t }, pues tan solo el autómata
podrá a un elemento x = t.

                -Hipótesis Inductiva: Supongamos que para un lenguaje Lp y Lq funciona, por lo tanto, si probamos que con un
                string de cardinalidad mayor se cumple, pues se hará válida la hipotesis de la inducción.
                Para ello es necesario demostrar todas las propiedades (+, · , *)

La definición de un x Î Lp es:
(" x) x Î Lp Ûp( e( Sp ), x ) Ç Fp ¹ Æ

Y para un y Î Lq es:
(" y) y Î Lq Ûq(e( Sq ), y ) Ç Fq ¹ Æ

L = P + Q

(" x) x Î L Û( e( S ), x ) Ç F ¹ Æ, partiendo de la fórmula original se tiene que:
(" z) L = P + Q Û p+q( e( Sp+q ), z ) Ç Fp+q ¹ Æ

Grafo Asociado a P + Q
S = Sp+q y F = { Fp, Fq }

                viendo el autómata se logra obtener una expresión equivalente a la original; donde
                p+q( e( Sp+q ), z ) = È (p +q( ( Sp+q ), x ) , p+q( ( Sp+q ), y))       "x Î Lp, "y Î Lq
                                                 = { Fp , Fq }

Esto significa que si z=x o z=y, entonces obtengo Fp o Fq que estan contenidos en el estado final de Fp+q,
lo cual implica que la intersección de Fp+q será distinto de vacío, por lo tanto z Î Lp+q

L = P · Q

(" x) x Î L Û( e( S ), x ) Ç F ¹ Æ, partiendo de la fórmula original se tiene que:
(" z) L = P · Q Û p·q( e( Sp·q ), z ) Ç Fp·q ¹ Æ

S = Sp y F = { Fq }

viendo el autómata se logra obtener una expresión equivalente a la original; donde

            p·q( e( Sp+q ), z ) = q( (p(e( Sp·q ), x)), y)       "x Î Lp, "y Î Lq
                                            = q( (Fp), y)
                                            = q( e(Sq), y)
                                            = Fq

            Esto significa que si z = x · y, entonces podemos partir de la clausura de Sp con "x" como primer string llego a Fp cuya
            clausura es Sq, y el resto del string "y" puedo obtener Fq por medio de su clausura, por ende Fq está contenido en el
            estado final de Fp·q, lo cual implica que la intersección es distinto de vacío, por lo tanto z Î Lp·q.

L = P*

(" x) x Î LÛ ( e( S ), x ) Ç Fp* Æ, partiendo de la fórmula original se tiene que:
(" z) L = P* Û p*( e( Sp* ), z ) Ç Fp* ¹ Æ

Grafo Asociado a P*
S = Sp* y F = { Fp* }

donde si z = Xn , p* se debe escribir como una función recursiva:

                                                                      - e      si n = 0
                                    p*(e( Sp* ), z) =
                                                                     -  p*((p( e( Sp* ), x)), Xn-1)

La función definida nos permite ver que para el caso de e estoy en el estado final (fin de la recursividad en la función), mientras que cualquier string de la forma Xn será reconocido por la función

p*, hasta que ese n sea igual a cero, por ende al alcanzar el fin de la recursividad tendremos:

                    p*(e( Sp* ), z) = p*(e( Fp* ), e)
                                               = e (Fp)
                                               = Fp*

Definición de AFD (Autómata Finito Determinístico)

Veamos con el ejemplo anterior: ( a + b) * a

e ´({1}) = {1,2,3,4,8,9} = {}
d ´´(e ´({1}),a) = {5,10}
e ´(d ´´(e ´{1}),a)) = {5,10,7,2,3,4,8,9} = {,}
d ´´(e ´({1}),b) = {6}
e ´(d ´´(e ´({1}),b)) = {6,7,2,3,4,8,9} = {}
d ´´ ({ ,},a) = {5,10}
e ´(d ´´({,},a)) = {,}
d ´´ ({,},b) = {6}
e ´(d ´´({,},b)) = {}
d ´´ ({ },a) = {5,10}
e ´(d ´´({},a)) = { ,}
d ´´ ({ },b) = {6}
e ´(d ´´({},b)) = { }

Se ha trabajado con d ´´ y solo con los subconjuntos de Q que interesan donde se tiene el estadio inicial clausura del estado inicial anterior (i.e. e ´({1}) = {}) y el (los) estado(s) final(es) es (son) aquel(los) c con un F anterior y es diferente al vacío.

Por construcción se puede ver que si un lenguaje es reconocido por un AFND, el mismo lenguaje es reconocido por el AFD construido en base al AFND, esto es:

Caso Æ: El resultado es el mismo grafo mostrado en el caso AFND, y se demostró que pertenece a L.

Caso e: Al sacar la clausura queda que el estado inicial y el final es el mismo, y ese autómata reconoce a e que pertenece a L.

Caso t: Al sacar la clausura queda el mismo grafo y se demostró anteriormente que t pertenece a L.

Caso P: Al sacar la clausura queda el mismo grafo y se demostró anteriormente que P pertenece a L.

Caso Q: análogo al caso P.

Caso P + Q: Al sacar la clausura quedan tres estados, el inicial, y dos finales que reconocen a P y a Q respectivamente, y se vió que en el caso P y Q ambos pertenecen a L.

Caso P.Q: Al sacar la clausura quedan tres estados, el estado inicial, el estado a donde llega P y el estado a donde llega Q (estado final), y se demostró anteriormente como P.Q pertenece a L.

Caso P*: Al sacar la clausura queda un estado final con un bucle que reconoce al estado P*

Esto es lo que se llama un AFD y se define como:

A = {Q,T, d ,S,F}
d :Q x T ® Q
SÎ Q
FÍ Q

Ejemplo:

T = {a,b}

Q = {1,2,3}

S = 1

F = {2}

d = {<<1,a>,2>,<<1,b>,3>,<<2,a>,2>,<<2,b>,3>,<<3,a>,2>,<<3,b>,3>}

Definición Formal de un Autómata Finito Determinístico (AFD)

Un AFD se define como una 5-tupla A = (Q, T, d , s, F) donde:

Q es un conjunto finito de estados.
T es el conjunto finito que denomina un alfabeto.
s Î Ü Q es el estado inicial.
F Í Q es el conjunto de estados finales.
d: Q x T ® Q es la función de transición.

Función de Reconocimiento de un AFD

Sea A = {Q,T, d , S, F} un AFD :

: Q x T* ® Q

(q, e ) = q

(q, tw) = ( d (q,t),w)

x Î L Û (S,x) Î F

Demostración:

(Þ) Si x Î L, entonces existe un autómata que lo reconozca, por lo tanto la función de reconocimiento para esa palabra sobre ese autómata que lo reconoce llega a un estado final.

(Ü) Si se tiene una función de transición definida sobre un estado inicial S y una palabra x que pertenece al conjunto de estados finales, esto quiere decir que el autómata reconoce a la palabra x por lo cual x Î L.

Ejemplo:

(1,aba) =

( d (1,a), ba) =

(2,ba) =

( d (2,b), a) =

(3,a) =

( d (3,a), e ) =

(2, e ) = 2 Î F

Puntos de Interés a investigar

¿Por qué cuando se calcula el AFD a partir del AFND, el proceso es finito? (i.e. llegamos a conjuntos calculados)

Si un lenguaje es reconocido por un AFND, se debe mostrar que existe un AFD que también lo reconoce, la idea es convertir el AFND en un AFD equivalente que simule el AFND.

Si k es el número de estados del AFND, entonces hay 2^ksubconjuntos de estados. Cada subconjunto corresponde a una de las posibilidades que el AFD debe tomar en cuenta, entonces el AFD simulando el AFND podría tener 2^k estados.

Sea N = (Q, T, d, s, F) un AFND que reconoce algún lenguaje L. Se construirá un AFD M que reconozca L. Primero se considera el caso en el cual N no tiene e , luego se tomará en cuenta.

Construimos M = (Q', T, d', s', F').

Q' = P(Q).

Cada estado de M es un conjunto de estados de N. (recordemos que P(Q) es el conjunto de subconjuntos de Q)

Para R Î Q' y a Î T. Se define d'(R,a) = {q Î Q| q Î d'(r,a) para algún r Î R}

Si R es un estado de M, es también un subconjunto de estados de N. Cuando M lee un símbolo a en el estado R, el muestra donde a toma cada estado en R, porque cada estado puede ir a un conjunto de estados, nosotros tomamos la unión de todos esos estados. Otra forma de escribir esta expresión es la siguiente:

s' = {s}.

M comienza en el mismo estado inicial que N

F' = {R Î Q'| R contiene un estado de final de N}

La máquina acepta si uno de los posibles estados en los que N podría estar es un estado final. Ahora necesitamos considerar los casos e. Para esto se extenderá la notación usada hasta ahora, para algún estado R de M definimos E(R) como una colección de estados a los cuales se puede llegar desde R sólo por alguna transición e, incluyendo los mismos miembros de R. Formalmente, para R Í Q se tiene E(R) = {q Î Q| q Î E( d(r,a)) para algún r Î R}. Adicionalmente necesitamos modificar el estado de inicio de M para mover sus apuntadores a todos los posibles estados que podrían alcanzar del estado inicial de N a lo largo de las transiciones e. Para esto cambiamos s' a E({s}), lo cual logra ese efecto. Hemos completado la construcción del ADF M que simula el AFND.

La construcción de M obviamente trabaja correctamente. En cada paso de cálculo de M sobre un input claramente entra a un estado que corresponde con un subconjunto de estados que N podría tener en ese punto.

Luego de esta demostración se puede ver que el proceso de transformación de un AFND a un AFD es finíto, ya que se parte de un conjunto k de estados del AFD y se llega a un conjunto 2^k posibilidades que debe tomar en cuenta el AFD.

¿Qué sucede si d es parcial?

Que d sea parcial indica que no está definida para ciertos valores. Esto implica que la función de reconocimiento no reconocerá todas las palabras pertenecientes a cierto lenguaje.

Por ejemplo si se tiene un autómata que reconoce todas las palabras que terminan en 0

Y tengo las siguientes funciones:

d(a,1) = a

d(a,0) = b

d(b,0) = b y supongo que esta última no esta definida.

Entonces la palabra 100, 1010, 1000... etc no son reconocidas ya que la función d es parcial. Sólo son reconocidas las palabras que tienen n cantidad de 1`s y un 0 al final.

¿Cómo totalizar d ?

Se puede totalizar d diciendo que cuando no tenga un valor se le asigna vacío.

Formalmente:

Si d(q,x) no está definido Þ d(r,a) = Æ donde q Î Q y x Î T È{e}

Por lo tanto se tiene que agregar las siguientes definiciones:

e'(Æ) = Æ

d''(Æ, t ) = d(Æ, t) = Æ

¿Qué sucede en los dos casos anteriores si queremos calcular el ? (i.e. el complemento del lenguaje)

El problema de construir el complemento del lenguaje a partir de una función parcial esta que nos lleva al cálculo sólo un subconjunto del complemento del lenguaje. Para calcular el complemento se deben transformar a todos los estados no finales en finales, y los que eran antes estados finales en no finales. Si la función es total, es decir, posee valor para cualquier letra del alfabeto, el autómata obtenido representará exactamente al complemento del lenguaje. En el caso de que la función es parcial y no esta definida para todos los elementos del alfabeto, entonces el autómata definido solo representará un subconjunto del lenguaje, ya que existirán palabras que no las reconocerá ni el autómata original ni el complemento del mismo.

Para mejor entendimieto ofreceremos un ejemplo.

FUNCION PARCIAL FUNCION TOTAL

Autómata que reconoce una serie de unos y luego una serie de ceros, o simplemente una serie de ceros
Autómata que reconoce el mismo lenguaje que el autómata de al lado

Complemento del autómata parcial

Complemento del autómata total

FUNCION PARCIAL	FUNCION TOTAL
Autómata que reconoce una serie de unos y luego una serie de ceros, o simplemente una serie de ceros	Autómata que reconoce el mismo lenguaje que el autómata de al lado
Complemento del autómata parcial	Complemento del autómata total

AFD Parcialmente especificado

Propiedad

Un autómata finito determinístico o AFD (å , Q, d , q₀, F) es parcialmente especificado si y sólo si d es función total.

AFD Completamente especificado

Propiedad

Un autómata finito determinístico o AFD (å , Q, d, q₀, F) es completamente especificado si y sólo si

* d es función total
* å x Q ® Q (cualquier elemento del dominio está definido)

K-Indistinguibles

Sea R_iÍ Q x Q, una relación de equivalencia (i=0, |Q|-2) y sean q₁, q₂ Î Q

q₁ =^k q_{2 «}<q₁, q₂> Î R_k « q₁ y q₂ son k-indistinguibles si y solo si "x Î å * long(x) £ k, entonces:

- (q₁, x) Ç F ¹ Ø Ù d' (q₂, x) Ç F ¹ Ø, llegan a estados finales

- (q₁, x) Ç F = Ø Ù d' (q₂, x) Ç F ¹ Ø, no llegan a estados finales

NOTA: Esta relación de equivalencia genera una partición.

Algoritmo de Minimización de un AFD

ENTRADA: M = (å , Q, d , q₀, F) un AFD total

SALIDA: M' = (å , Q', d', q₀', F') un AFD que reconoce el mismo lenguaje que M pero con la menor cantidad de estados posible.

1.- Construir la partición inicial P : Finales y no Finales (G₁=F y G₂=Q-F)
2.- Para cada grupo G_i de la partición P (G_i Î P)

2.1.- Particionar G_i en subgrupos siempre que dos estados s y t de G_i estarán en el mismo grupo si y solo si dichos estados, a través de una transición "a" llegan a estados que están en el mismo grupo G_i de la partición P . En el peor de los casos un subgrupo contendrá un solo elemento.
2.2.- Reemplazar G_i por los nuevos subgrupos de G_i para crear la nueva partición P _nuevo. 3.- Si P =P _nuevo, P _final=P
Sino volver al paso 2.
4.-Q'={G_i/ G_i Î P _final} (Los nuevos estados del autómata, son las particiones de P _final)
q₀'= G_i/ G_iÎP _final y q_{0 Í}G_i (El nuevo estado inicial q₀' es el grupo que contiene a q₀)
F'={G_i/ G_iÎP _final y $ f Î F/ f Î G_i} (Los nuevos estados finales son todos los grupos de las particiones que contiene estados que estaban en los estados finales
del autómata original, es decir en M)
Finalmente el autómata minimizado es M'=(å , Q', d', q₀', F') (Las nuevas transiciones son todas aquellas que existen en el autómata inicial que unen los nuevos estados del autómata. No deben haber transiciones repetidas)

Para el caso en que un autómata tenga varios estados finales, la partición inicial no debe ser estados finales y estados no finales, ya que cada estado final reconoce palabras distintas, dado que el autómata es determinístico. Por lo tanto, la partición debe ser estados no finales y cada estado final debe pertenecer a una partición diferente.

Reconocimiento del mismo lenguaje por el AFD y por el AFD Mínimo Equivalente

¿L(M) = L(M')?

Se va a verificar si el lenguaje reconocido por un AFD es el mismo lenguaje que el reconocido por su AFD Mínimo equivalente.
Veamos las transiciones del autómata M'

d'={ <G_i, a, G_j> / <g_i, a, g_j>}Î d Ù g_i Î G_i Ù g_j Î G_j}
Para la creación de d' se toma cada una de las transiciones de M, adaptándolas según la definición. Como "todas" las transiciones del autómata original son tomadas en cuenta, el lenguaje generado es el mismo.
Sin embargo, |d | ³ |d'| y esto se debe a que al generar d' pueden aparecer arcos repetidos porque G_i y G_j contiene uno o varios estados del autómata original.

Teorema de Unicidad

Teorema: El autómata mínimo es único para cada lenguaje regular.

Demostración: Para un autómata de k estados |Q|=k, se necesitan a lo más k-2 pasos para obtener el autómata mínimo asociado (siguiendo el algoritmo antes especificado)

Haciendo inducción sobre k (número de estados).

|Q|=k=2

P :

G₁=F, |F|=1

G₂=Q-F, |Q-F|=1

Si hay dos estados, uno debe ser el inicial y otro el final, lo que significa que la partición inicial de cada grupo tiene un elemento y no se puede seguir subdividiendo, por lo tanto número de paso requeridos es cero (0).
k-2=2-2=0 (se cumple)

|Q|=k=3

Si hay tres (3) estados se tienen dos casos: que hayan dos estados finales y uno no final o que haya un estado final y dos no finales.

Caso1:

P :

G₁=F, |F|=2

G₂=Q-F, |Q-F|=1

A lo más se puede realizar un paso en el cual se divida G₁en dos subgrupos de un elemento cada uno.

k-2=3-2=1 (se cumple)

Caso2:

P :

G₁=F, |F|=1

G₂=Q-F, |Q-F|=2

A lo más se puede realizar un paso en el cual se divida G₂en dos subgrupos de un elemento cada uno.

k-2=3-2=1 (se cumple)

Hipótesis Inductiva:

Para un autómata de k estados |Q|=k, se necesitan a lo más k-2 pasos para obtener el autómata mínimo asociado a éste.

P :

G₁=F, |F|=t

G₂=Q-F, |Q-F|=k-t

Se necesitan k-2 pasos, cuando se tienen Q=Q', es decir, necesita hacer tantos pasos en la minimización como sean necesarios para poder tener cada subgrupo de un solo elemento.

Tesis Inductiva:

P :

G₁=F, |F|=p

G₂=Q-F, |Q-F|=k+1-p

Por hipótesis inductiva, en el peor de los casos después de k-2 pasos, se tiene una partición que tenga todos los grupos de un solo elemento, exceptuando un grupo de dos elementos, si en este punto es necesario otro paso el único posible será subdividir el grupo de cardinalidad 2. Lo cual, significa que la minimización tomó k-2+1 casos, por lo tanto, se cumple para |Q|=k+1.

Ejemplo:

Sea el AFD=({0,1}, {A,B,C,D,E,F}, d, A,{E,F})

donde d={<A,0,B>, <A,1,D>, <B,1,B>, <B,0,C>, <C,0,E>, <C,1,D>, <D,1,D>, <D,0,F>, <E,0,E>, <E,1,F>, <F,0,E>, <F,1,F>}

Se sabe que se tienen que hacer n-2 pasos, es decir, 6-2=4 pasos hasta llegar a la "Minimización" de AFD .

Sea la primera partición la siguiente, formada por los estados no finales (no terminales) y los finales (terminales): (k=0)

a) {A, B, C, D} b) {E, F}

Se verán ahora las frases de longitud igual a 1, se verifica si se llega (S) o no (N)a un estado final, entonces trabajando con a) se tiene lo siguiente:

Frases/ No Teminales A B C D

0 N N S S

1 N N N N

Como la cuarta columna al igual que la quinta de se comportan de manera diferente, se realiza una nueva partición (k=1)

{A, B }

{C, D}

{E, F}

Veamos ahora que ocurre con {A, B}

Frases/ No Teminales	A	B
00	N	S
11	N	N
01	N	N
10	S	N

Veamos ahora que ocurre con {C, D}

Frases/ No Teminales	C	D
00	S	S
11	N	N
01	S	S
10	S	S

Como con {A, B} se comportan de manera diferente se realiza otra partición (k=2)

{A}

{B}

{C, D}

{E, F}

Veamos ahora que ocurre con {C, D} para frases de longitud =3

Frases/ No Teminales	C	D
000	S	S
111	N	N
001	S	S
010	S	S
101	S	S
110	S	S

Como con {C, D} se comportan de igual manera se conservan las mismas particiones (k=3)

{A}

{B}

{C, D}

{E, F}

Por lo tanto de aquí en adelante se conservan las mismas particiones (k=4)

Así que el AFD minimizado será el siguiente:

Min(ADF)= ({0,1}, {A,B,C-D,E-F}, dmin, A,{E-F})

Lema del Bombeo (Pumping Lema)

Si L es regular, un AFD A=(Q, T, d , S, F) que reconoce a L

("w) [ w Î L y long(w) ³ |Q| ® (x,y,z) T* Ù ($ y): w = x.y.z Ù 0 < long |y| £ long (w)]
x.yⁱ.z L

Si el lenguaje es infinito tiene que haber un elemento estrella en la Expresión Regular.

w = t₁, t₂, ... , t_m m ³ |Q|

q₀ ®^t₁ q₁ ®^t₂ q₂ ... ®^t_n-1 q_n-1®^t_nq_n

Se repite al menos un estado

t_k ... t_k+j
q_k ... q_k+j son iguales ® q_k = q_k+j, j >0, y= t_k+1... t_k+j,el loop es t_k+1... t_k+j

Si la longitud de alguna de las expresiones que forman el lenguaje es mayor que estados, entonces el Lenguaje es
infinito |L| = ¥

Otra Visión de los AFD y de los AFND

Existe otra manera de representar a los autómatas, la cual consiste en la utilización de "Gramáticas Regulares".

Sea el AFD A=(Q, T, d , S, F), donde: d : Q x T ® Q

Se define el conjunto de producciones de la siguiente manera:

P Í Q x ((T.Q) È {e }) " <<q, t>, q'>Î d Þ <q, tq'> Î P " q Î F Þ <q, e> Î P

El alfabeto T, representa los elementos terminales de la gramática, mientras que el conjunto de estado Q representa los elementos no terminales.

Esto se llama una gramática regular (lineal a la derecha) y se representa como:

G=(Q, T, P, S) <a , b > Î P Û a ® b

Ejemplo:

Sea la gramática G₁ = ({S,A},{a,b}, P₁, S) donde P₁ = {S ® aA, S ® bS, A ® bS, A ® aA, A ® e}

Lenguajes Regulares

Teorema

Las siguientes proposiciones son equivalentes:

* L es un Lenguaje Regular
* L es denotado por alguna expresión regular
* L es reconocido por algún AFND (Autómata Finito no Determinístico)
* L es reconocido por algún AFD (Autómata Finito Determinístico)
* L es generado por alguna Gramática Regular.

Gramáticas Libres de Contexto

Definición

Una gramática libre de contexto (o independiente del contexto) es una 4-tupla (N, S , P, S) donde

* N es un conjunto finito no vacío cuyos elementos son llamados símbolos no terminales
* S es el alfabeto a cuyos elementos se le llaman símbolos terminales
* P Í N x (N È S )* cuyos elementos son llamados producciones
* S Î N es el símbolo inicial

- Notación

Las producciones (A,µ) se denotan A ® µ con

A Î N (Símbolo no terminal)
µ Î (N È S )* (Combinación de elementos pertenecientes al conjunto de los terminales y los no terminales)

Definición General de Gramática Regular Lineal a la Derecha

Sea G = (N, T , P, S) una gramática general regular donde:

* |N| < ¥ y N ¹ Ø Conjunto de símbolos no terminales
* |T| < ¥ y T ¹ Ø Conjunto de símbolos terminales
* S Î N Axioma o símbolo objetivo
* |P| < ¥ y P Í ((N È T)* N (N È T)*) x (N È T)* Conjunto de Producciones,
<µ , b > Î P Û µ ® b

Lenguaje Generado por una gramática G (L(G)) Sea P ¹Ø el conjunto de producciones: P Í ((N È T)* N (N È T)*) x (N È T)* (En este caso se obliga a que exista un símbolo no terminal.)
P Í (N È T)* x (N È T)*

Substituciones (Derivaciones)

Definición:

La relación de derivación directa (o generación directa) Þ _G es un subconjunto D, tal que

l = d₁.a .d₂ Ù l Þ _G g Û <l , g >

D Û g = d₁.b .d₂ Ù a ® b

P Ù

(d₁,d₂(N È T)*); aN; b(N È T)*

(NOTA: Si en l hay una ocurrencia de la parte izquierda de las producciones, entonces se puede cambiar esa ocurrencia por la parte derecha de la producción.)

La relación de derivación general (o generación general) es la clausura reflexiva-transitiva de Þ _G, es decir Þ _G^*

Explicación: Se hace la clausura reflexiva-transitiva de D (Þ _G) , es decir D*

<l , g > D Þ <l , g > D*
l (N È T)* Þ <l , l > D*
<l , g > D* Ù <g , Y > D* Þ <l , Y > D*

D* Û l Þ ^* g

P Í D Í D*

El lenguaje L(G) generado por una gramática se define como:

L(G)={x ½ x T* Ù SÞ ^*x}

"A Î N:

L(A)={ x ½ x Î T* Ù AÞ ^*x }

L(S)= L(G)

Para recordar que la derivación es según las producciones de la gramática G:

L(A)={ x ½ x Î T* Ù AÞ _G^*x }

(NOTA: Sólo las frases que comienzan por el símbolo no terminal 'S' pertenecen al lenguaje generado por una gramática que contiene a ese símbolo inicial.)

Ejemplo: Sea la gramática G₁=({S,A}, {0,1}, P₁, S) con P₁ compuesta por:
              S ® SA (0),
              S ® 0 (1),
              S ® 1A1 (2),
              A ® 0 (3)
Un ejemplo de frase generada por G₁ es: 00
S Þ ⁽⁰⁾ SA Þ ⁽¹⁾ 0A Þ ⁽³⁾00
Por lo tanto, S Þ ^* 00
Por lo tanto 00

L(G₁)
Ejemplo:

Sea la gramática G=(N,T,P,S)
      N={S, A}
      T={a, b}
      P={S ® aA, S ® bS, A ® bS, A ® aA, A ® e }
      S Î N

Se verá como a partir de una gramática dada se obtiene la expresión regular asociada:
A partir de las producciones de la gramática G se obtienen dos incógnitas, una por cada lenguaje:

L(S)={a}.L(A) È {b}.L(S)
L(A)={a}.L(A) È {b}.L(S) È {e}
L(S)=a.L(A)+b.L(S)
L(A)=a.L(A)+b.L(S)+e

Ahora, bien se tienen las siguientes ecuaciones:
S=aA+bS
A=aA+bS+e = aA+(bS+e) asociando los dos últimos términos.
Utilizando x=a x+b Þ x=a *b (1), se obtiene:
A=a*(bS+ e)
Sustituyendo el valor de A en S, se obtiene:
S=a(a*(bS+ e))+bS
S=aa*bS + aa* + bS = aa*bS + bS + aa*, factorizando
S=(aa* + e)bS + aa*
Utilizando el axioma de expresiones regulares e+(a.a*) = a*
S=a*bS + aa*
Usando nuevamente (1), se tiene que:
S=(a*b)*aa(a+b)*a

Ejemplo:

Sea el autómata A₁=({S,A,B},{a,b}, d , S, {A,B}), donde d ={<S,a,A>, <S,b,B>, <A,a,A>, <A,b,B>, <B,b,B>, <B,a,A>} y la gramática asociada G₁=({S,A,B}, {a,b}, P₁, S)

P₁={S ® aA, S ® bB, A ® aA, A ® aB, A ® e, B ® bB, B ® bA, B ® e}

    L(S)={a}.L(A) È {b}.L(B)
    L(A)={a}.L(A) È {b}.L(B) È e
    L(B)={b}.L(B) È {a}.L(A) È e

    L(S)=a.A+b.B
    L(A)=a.A+b.B+e
    L(B)=b.B+a.A+e

    S=aA + bB
    A=aA + bB + e
    B=aA + bB + e = bB + (aA + e), asociando
    Usando (1), se tiene que:
    B=b*(aA+e )
    Sustituyendo el valor de B en A:
    A=aA + b(b*(aA+ e)) + e
    A=aA + bb*aA + bb* + e
    A=(a + bb*a)A+ bb* + e
    A=b*aA+ b* Usando (1) se tiene que: A=(b*a)*b*

Se sustituye el valor de A en B
B=b*(a(b*a)*b* + e)

Se sustituye el valor de A y el de B en S
S=a(b*a)*b+ bb*(a(b*a)*b* + e )

Tipificación de las Gramáticas (Chomsky)

Sea G = (N, T , P, S) donde

* | N | < ¥ y N ¹ Ø
* | T | < ¥ y T ¹ Ø
* N Ç T= Ø
* S Î N
* | P | < ¥ y P Í ((N È T)* N (N È T)*) x (N È T)* Tipo 0: No hay restricciones sobre P

Tipo 1: (Dependientes del contexto o context Sensitive)
" µ ® b Î P
long(µ ) £ long(b )

Tipo 2: (Independientes del contexto o context Free) Análisis Sintáctico
" µ ® b Î P
long(µ ) = 1

Tipo 3: (Gramáticas Regulares) Análisis Lexicográfico
* Lineal a la izquierda
" µ ® b Î P
µ Î N y b Î (N È {e }) .T*
* Lineal a la derecha
" µ ® b Í P
µ Î N y b Î T* . (N È {e })

Autómatas de Pila

Autómatas Finitos con control sobre.

cinta de entrada, y
pila de entrada/salida

Se extiende la función de movimiento (d ) para que dependa de:

el estado actual,
el caracter en la cinta ( o e ), y
el símbolo del tope de la pila.

Como resultado de realizar un movimiento:

se consume el caracter de la cinta y el tope de la pila,
se cambia de estado,
se empila nuevos símbolos

Definición de Autómatas de Pila

Un ADP es una máquina M = ( Q , S , G , d , q₀ , Z₀ , F ) donde

Q es un conjunto finito de estados,
S es el alfabeto de la entrada
G es el alfabeto de la pila,
q₀ Î Q es el estado inicial,
Z_{0 Î}G es el tope de la pila inicial,
F Í Q es el conjunto de estados finales, y
d : Q x (S È {e }) x G à 2^QxF^* es la función de transición

Donde la función de transición d se interpreta:

d ( q, a, Z ) = {(p₁_{g 1})… (p_m_{g m})}

El autómata se puede mover del estado q al estado p_i(1 < i < m) al observar a en la entrada y Z en el tope de la pila. En ese caso,

se avanza el cabezal de la cinta, y
se reemplaza Z por g _i
d ( q, e , Z ) = {(p_{1g 1})… (p_{mg m})}

El autómata se puede mover del estado q al estado p_i(1 < i < m) independientemente de la cinta al observar Z en el tope de la pila. En ese caso,

se reemplaza Z por g _i

En todo Autómata de pila se puede definir:

Configuración Inicial

Se define de la forma (q₀ , w) para cualquier w Î S *

Configuración Final

Se define de la forma (a f, e ) para cualquier a Î Q* y f Î F

Movimiento

Se define como una relación |¾ al subconjunto de (Q* x S *)x(Q* x S *) t.q

(a , w) |¾ (a ', w') ssi

a = a ₁ a ₂

a ' = a ₁ a ₃

w = aw'

(a ₂, a, a ₃) Î d

Para algún

a ₁ Î Q*, a ₂ Î Q*, a ₃ Î Q*

a Î S * È {e }

Ejemplos de un autómata de pila.

Sea P₁ = ( { 0, 1 } , { E, R, S, C, U, B} , d , E, {R} )

Donde definimos a d como los siguientes movimientos:

(E, e , ES)

(S, 0, CS)

(S, 1, V)

(S, e , B)

(CB, 0, B)

(UB, 1, B)

(EB, e , R)

¿La secuencia "00" pertenece al lenguaje reconocido por P_1. ?

Primer intento

(E, 00) |¾ (ES,00) |¾ (ECS, 0) |¾ (ECCS, e ) |¾ (ECCB , e )

Fallo, el estado final no es válido, es decir, no es una configuración final

Segundo intento

(E, 00) |¾ (ES,00) |¾ (EB, 00) |¾ (R, 00)

Fallo, el estado final no es válido, es decir, no es una configuración final

Tercer intento

(E, 00) |¾ (ES,00) |¾ (ECS, 0) |¾ (ECB, 0) |¾ (EB , e ) |¾ (R, e )

Reconocido, el estado obtenido es una configuración final.

¿La secuencia "010" pertenece al lenguaje reconocido por P_1. ?

(E, 010) |¾ (ES,010) |¾ (ECS, 10) |¾ (ECUS, 0) |¾ (ECUB ,0)

Fallo, el estado final no es válido, es decir, no es una configuración final.

¿La secuencia "0110" pertenece al lenguaje reconocido por P_1. ?

(E, 0110) |¾ (ES,0110) |¾ (ECS, 110) |¾ (ECUS, 10) |¾ (ECUB ,10) |¾ (ECB ,0) |¾ (EB , e ) |¾ (R, e )

Reconocido, el estado obtenido es una configuración inicial.

Definición de Gramática Extendida

Sea G = (N, S , P, S), una gramática libre de contexto cualquiera.

Se define GRAMATICA EXTENDIDA de G como G' = (N', S , P', S') donde:

N'= N È {S'} con S'Ï N y P' = P È {S' ® S}

Un Item de G es una 3-tupla (A, a , b ) con A ® a b Î P' y se denota como

[A ® a .b ]

Ejemplo:

G = ({S,A}, {0,1,2,3}, P, S)

Donde P corresponde a las producciones:

S ® 0A1

A ® 2A

A ® 3

A ® e

Entonces G' = ({S', S, A}, {0,1,2,3}, P, S')

Donde P corresponde a las producciones:

S'® S

S ® 0A1

A ® 2A

A ® 3

A ® e

Entonces, los items de G son:

[S' ® .S] (No se ha reconocido S) [A ® .3]

[S' ® S.] (Ya se reconoció S) [A ® 3.]

[S ® .0A1] ..... [A ® .2A]

[S ® 0.A1] [A ® 2.A]

[S ® 0A.1] [A ® 2A.]

[S ® 0A1.] [A ® .]

Definición de Autómatas de Pila de Items de G

Dada una gramática libre de contexto G = (N, S , P, S) con gramática extendida G' = (N', S , P', S'), el AUTOMATA DE PILA DE ITEMS de G es:

K_g = (S ,I_tg, D , [ S' |¾ S], F)

Donde d se define como

{ ( [A |¾ a .Bb ] , e , [A |¾ a .Bb ] [B |¾ .g ] ) | A Î N' ; B Î N ; a ,b ,g Î (N È S )* ; A |¾ a Bb Î P' ;

B |¾ g Î P } Transiciones de Expansión à se empilan

È "unido"

{ ( [A |¾ a .xb ] , x , [A |¾ a .xb ] ) | A Î N' ; x Î S ; a ,b Î (N È S )* } Transiciones de Lectura

È "unido"

{ ( [A |¾ a .Bb ] [B |¾ g .] , e , [A |¾ a B.b ] ) | A Î N' ; B Î N ; a ,b ,g Î (N È S )* ; A |¾ a Bb Î P' ;

B |¾ g Î P } Transiciones de Reducción à se desempilan

Ejemplo:

Obtener K_G1de:

G1 = ({S,A}, {0,1}, P1, S)

Donde P1 corresponde a las producciones:

S'® S

S ® AS

S ® e P1 P1'

A ® 0

Se tiene que los Items de G' son:

[S' ® .S]

[S' ® S.]

[S ® .AS]

[S ® A.S]

[S ® AS.]

[S ® .]

[A ® .0]

[A ® 0.]

D = {([S' ® .S], e , [S' ® .S] [S ® .AS]),

([S' ® .S], e , [S' ® .S] [S ® .]),

([S ® .AS], e , [S ® .AS] [A ® .0]),

([S ® A.S], e , [S ® A.S] [S ® .AS]),

([S ® A.S], e , [S ® A.S] [S ® .]),

([A ® .0], 0, [A ® 0.]),

([S' ® .S] [S ® AS.], e , [S' ® S.]),

([S' ® .S] [S ® .], e , [S' ® S.]),

([S ® .AS] [A ® 0.], e , [S ® AS.]),

([S ® A.S] [S ® AS.], e , [S ® AS.]),

([S ® A.S] [S ® .], e , [S ® AS.])}

K_G1 = ({0, 1}, I_TG, D, S' ® S, {[S' ® S]})

([S' ® .S], 00)

|¾ ([S' ® .S] [S ® .AS], 00)

|¾ ([S' ® .S] [S ® .AS] [A® .0], 00)

|¾ ([S' ® .S] [S ® .AS] [A® 0.], 0)

|¾ ([S' ® .S] [S ® A.S], 0)

|¾ ([S' ® .S] [S ® A.S] [S® .AS], 0)

|¾ ([S' ® .S] [S ® A.S] [S® .AS] [A® .0], 0)

|¾ ([S' ® .S] [S ® A.S] [S® .AS] [A® 0.], e)

|¾ ([S' ® .S] [S ® A.S] [S® A.S], e)

|¾ ([S' ® .S] [S ® A.S] [S® A.S] [S® .], e)

|¾ ([S' ® .S] [S ® A.S] [S® AS.], e)

|¾ ([S' ® .S] [S ® AS.], e)

|¾ ([S' ® S.], e)

Autómatas de Pila con Salida

Autómata de pila sin salida

Autómata de pila con salida

M1 = ( Q, S , d , q₀, F )

d Í Q⁺x (S È {e}) x Q^*

Configuración Î Q^*x S ^*

Configuración Inicial: (q₀, w)

Configuración Final: (af, e), con a Î Q^*

Ejemplo:

Ap sin salida: ({A, B}, {0, 1}, {(A, 0, AB), (B, 1, e)}, A, {A, B}

Frases reconocidas

(A, 0) |¾ (AB, e) 0

(A, 1) |¾ X 1

(A, 001) |¾ (AB, 01) |¾ X ~~001~~

(A, 01) |¾ (AB, 1) |¾ (A, e) 01

M2 = ( Q, S , G , d , q₀, F )

d Í Q⁺x (S È {e}) x Q^*x (G È {e})

Configuración Î Q^*x S ^* x G ^*

Configuración Inicial: (q₀, w, e)

Configuración Final: (af, e, v), con v Î G ^*
Ejemplo:

Ap con salida: ({A, B}, {0, 1}, {x, y}, {(A, 0, AB, e), (B, 1, e, x)}, A, {A, B}

Frases reconocidas

(A, 0, e) |¾ (AB, e, e) 0
(A, 1, e) |¾ X 1
(A, 001, e) |¾ (AB, e, 01) |¾ X ~~001~~
(A, 01, e) |¾ (AB, e, 1) |¾ (A, e, x) 01

Definición de Gramática LL(K)

Para definir que es una gramática LL(k), debemos comenzar hablando de gramáticas ambíguas.

Una gramática es ambígua si se cumplen las siguientes propiedades:

                                   - L (G) ={ w / w Î T* Ù S Þ* w}
                                   - G = ( N, T, P, S )        | N | £| P |
                                   - (" A Î N)    S Þ* aAb
                                                          A Þ* w Î T*

             Esto quiere decir que se puede conseguir más de un árbol de derivación que exprese la misma gramática.
             La causa de ello, es la falta de prioridad definida en el lenguaje, como LL(k) permite expresar prioridad en el
             lenguaje, se puede decir entonces que LL (k) no es ambígua.

Para ilustrar la idea de una gramática LL(k), se pudiese ver como que los nodos terminales son representados
entre < > y los nodos terminales son elementos pertenecientes al alfabeto T.

             Por ejemplo:
                        < condicion_if > :: = if < expresión > then < instrucciones >
                                                          < opcional_else > fi
                        Donde el conjunto N={ expresión, instrucciones, opcional_else } y T={ if, then, fi }

Su representación gráfica (árbol de derivación) se manipula bajo el concepto de top-down, haciendo que su
método de parseo sea sencillo.

Más aún su interpretación es inmediata, para el ejemplo anterior se diría que siempre una < condicion_if >
comienza con " if " y finaliza con " fi ", proviendo suficiente información para la creación del árbol.

Ahora se explicará los conceptos basicos para entender LL(k), nos enfocaremos para el caso k=1.

	V si X Þ* e
- seAnula (X) =
	F sino

- primero (X) = { t | t Î T Ù X Þ* tw para algun w Î T* }

- siguiente (X) = { t | t Î T Ù S Þ* uXtw para algun u,w Î T* }

- director (A ® X1X2......Xn) = È primero (Xi) È (if seAnula(X1X2...Xn) then siguiente(A) else Æ)

Una gramática G es LL(1) Û A ® a | b son 2 producciones distintas de G y cumplen las siguientes condiciones:

1. Para a y bÎ N, $a / se puede derivar en ambos casos un string que comience con "a".

2. Al menos uno entre a y b, se puede derivar en el string vacío.

3. Si b Þ* e, entonces a no deriva en otro string que comience con un nodo terminal en el siguiente (A).

Para que se cumplan estas condiciones, se debe tener que:

" (A ® X1X2.....Xn) (A ® Y1Y2....Ym) Û director (A ® X1X2....Xn) Ç director (A ® Y1Y2......Ym) = Æ

Esto asegura que "A Î N se cumplen las condiciones anteriores.

En términos generales las gramáticas LL(k) implica que se necesitan k elementos para saber que producciones se debe
escoger para reconocer un string de un lenguaje determinado.

Una gramática con derivación más a la izquierda nunca será fuertemente LL(k) para ningún valor de k.

Definición de una gramática fuertemente LL(k): Una gramática G fuertemente LL(k) con un k>0 fijo, se define
como una gramática que tenga la siguiente característica:

                 Sea la producción A ® a y A ® b en P con el mismo lado izquierdo,al obtener el director de ese conjunto
                 de producciones y es además capaz de escoger entre 2 producciones, pues podemos garantizar la condición de
                 fortaleza si la intersección entre los k-ésimos directores es igual al vacío.

Definición de una gramática débil LL(k): Una gramática G debilmente LL(k) con un k>0 fijo, se define como
una gramática que tenga la siguiente característica:

                 Sea la producción A ® a y A ® b en P con el mismo lado izquierdo,al obtener el director de ese conjunto
                 de producciones y es además capaz de escoger entre 2 producciones, pues garantizar la condición de debilidad
                 si la intersección entre los k-ésimos directores es distinta al vacío.

Definición de Gramática LR(K)

Suponga G=(Vn, Vt, P, S) es una gramática libre de contexto y G’=(Vn’, Vt’, P’, S’) la gramática extendida de G obtenida al agregarle a G un nuevo símbolo S’ y la producción S’® S entonces G’ es una gramática LR(k) si:

S’® aXw ® aBw

S’® rYx ® aBy

k:w=k:y entonces

a=r, X=Y y x=y

Suponga S=a₀ ® a₁ ® a₂ ... ® a_n = v es una derivación más a la derecha para una gramática G libre de contexto. G será una gramática LR(k) si para cada derivación el asa puede ser localizada y si la producción a ser aplicada puede ser determinada.

Reconocedores predictivos pueden ser descendentes (top-down o LL(k)) o ascendentes (bottom-up o LR(k))

Teorema

Teorema: Si LL(K) entonces LR(k)

Los lenguajes LR son los lenguajes que pueden ser reconocidos por un autómata de pila determinístico (ADPD).

Los reconocedores ascendentes LR construyen el árbol de derivación comenzando desde las hojas hasta la raíz y en post orden (derivación más a la derecha).

Un asa (handle) es una subpalabra que corresponde con una parte derecha de una producción tal que su reemplazo por la parte izquierda correspondiente representa un paso a través de una derivación más a la derecha.

Si la gramática no es ambigua entonces existe un asa única para cada forma sentencial.

Operaciones de un Reconocedor Shift Reduce

[empilar] (shift) el carácter de la entrada se consume y es empilado.

[reducir] (reduce) en el tope de la pila esta es la parte derecha de un asa, la cual reemplazará por un no terminal para ello:

- se debe conocer cual es la longitud del asa

- se debe conocer por cual producción reducirla.

El terminal de la entrada no es consumido.

[aceptar] (accept) El analizador acepta la entrada.

[error] (error) El analizador encontró un error sintáctico

Ejemplo

Considere la siguiente gramática:

G = (N, T, P, E)

Con P = { E®E+E

E®E*E

E® (E)

E®id }

Derivación más a la derecha de id + id * id

E®E+E

®E+E*E

®E+E*id

®E+id*id

®id+id*id

Reconocimiento de id+id*id

Pila	Entrada	Acción
	id+id*id	Empilar
Id	+id*id	Reducir E®id
E	+id*id	Empilar
E+	id*id	Empilar
E+id	*id	Reducir E®id
E+E	*id	Empilar
E+E*	id	Empilar
E+E*id		Reducir E®id
E+E*E		Reducir E®E*E
E+E		Reducir E®E+E
E		Aceptar

Introducción a las Gramáticas SLR(1)

No existe un analizador sintáctico SLR(1) para toda gramática canónica LR(1). Recíprocamente, toda gramática que tiene un analizador sintáctico SLR(1) es una gramática LR(1).

El punto de partida por la construcción práctica de un analizador sintáctico SLR(1) es un analizador sintáctico LR(0) que ha sido previamente construido. Para eliminar los estados inadecuados, los items completos dentro de los estados LR(0) son extendidos por conjuntos "lookahead".

Definición de Gramática SLR(1)

Supóngase los items de un autómata característico de pila K para una gramática G son extendidos de la manera que se describió arriba usando los conjuntos "lookahead".

Un estado es inadecuado si:

- dos items [X₁®a₁.,L₁] y [X₂®a₂. ,L₂] con L₁ÇL₂¹Æ

- dos items [X®a.ab] y [Y®g. ,L] con aÎL

Si no hay estados inadecuados, entonces G es una gramática SLR(1)

NOTA:

Para obtener un SLR(1):

A los items de reducción de la forma [A®a.] se les agrega el siguiente "lookahead":

{a Î S È {#}| S'# Þ_der^* bAaw}, es decir, el SIGUIENTE (A)

De esta manera se eliminan los conflictos.

Ejemplo:

Sea la gramática G con las siguientes producciones:

S ® E

E ® E+T | T

T ® T*F | F

F ® (E) | id

Los estados del autómata asociado son los siguientes:

S₀={[S®.E], [E®.E+T], [E®.T], [T®.T*F], [T®.F], [F®.(E)], [F®.id]}

S₁={[S®E.], [E®E.+T]}

S₂={[E®T.], [T®T.*F]}

S₃={[T®F.]}

S₄={[F®(.E)], [E®.E+T], [E®.T], [T®.T*F], [T®.F], [F®.(E)], [F®.id]}

S₅={[F®id.]}

S₆={[E®E+.T], [T®.T*F], [T®.F], [F®.(E)], [F®.id]}

S₇={[T®T*.F], [F®.(E)], [F®.id]}

S₈={[F®(E.)], [E®E.+T]}

S₉={[E®E+T.], [T®T.*F]}

S₁₀={[T®T*F.]}

S₁₁={[F®(E).]}

Los estados S₁, S₂y S₉ son inadecuados.

Se extienden los items completos de cada uno de dichos estados utilizando la definición de SIGUIENTE. Entonces se obtiene lo siguiente:

S₁''= {[S®E.,{#}], [E®E.+T]} El conflicto fue eliminado: "+" no pertenece a {#}

S₂''={[E®T., {#, +, )}], [T®T.*F]} El conflicto fue eliminado: "*" no pertenece a {#, +, )}

S₉''={[E®E+T., {#, +, )}], [T®T.*F]} El conflicto fue eliminado: "*" no pertenece a {#, +, )}

Entonces, G es una gramática SLR(1)

Ejemplo:

Sea la gramática G con las siguientes producciones:

S' ® S

S ® L=R | R

L ® *R | id

R ® L

El conjunto de items, que forman los estados del autómata asociado son los siguientes:

S₀={[S'®.S], [S®.L=R], [S®.R], [L®.*R], [L®.id], [R®.L]}

S₁={[S'®S.]}

S₂={[S®L.=R], [R®L.]}

S₃={[S®R.]}

S₄={[L®*.R], [R®.L], [L®.*R], [L®.id]}

S₅={[L®id.]}

S₆={[S®L=.R], [R®.L], [L®.*R], [L®.id]}

S₇={[L®*R.], [L®.id]}

S₈={[R®L.]}

S₉={[S®L=R.]}

S₂ es un estado inadecuado y el SIGUIENTE(R)={#,=}. Cuando el item [R®L.] es extendido con el conjunto "lookahead", el conflicto shift-reduce se mantiene, ya que el símbolo "=" a ser leído está contenido en le conjunto "lookahead" ({#,=}) del item mencionado, por lo tanto G no es una gramática SLR(0).

pagina original: http://www.ldc.usb.ve/~soler/traductores3/

Hosted by www.Geocities.ws