Autómatas con Pila y Analizadores Sintácticos de M.a.paz Menvielle

UNIDAD 5: AUTÓMATAS CON PILA

ANALIZADORES SINTÁCTICOS

M.A.Paz Menvielle 2k3-2k11

CONTENIDOS

• Autómata con Pila (AP)
• Definición
• Configuración
• Movimiento
• Aceptación de cadenas
• Tipos: APD-APND
• Ejemplos
  • Analizadores Sintácticos
  • ASD
  • ASA

M.A.Paz Menvielle 2k3-2k11

AUTÓMATAS CON PILA

M.A.Paz Menvielle 2k3-2k11

AUTÓMATAS CON PILA: AP

• Autómatas Finitos Lenguajes Regulares.
• Hay lenguajes que no son regulares: {0~1n / n ≥ 1; 0 1 n=1 L={01} 0 1 2 0 0 1 1 n=2 L={0011} 0 1 2 3 4 0 0 0 1 0 1 2 3 4 n=3 L={000111} 1 1 6 5 . .. n=k , se necesitarán 2k+1 estados (AF usa estados para contar). No se puede hacer un AF que acepte todo el lenguaje.

M.A.Paz Menvielle 2k3-2k11

AUTÓMATAS CON PILA: AP

• {0"1" / n ≥ 1} nos hace ver que para poder aceptar este lenguaje no regular se necesita alguna forma de poder "contar" cuántos símbolos 0 han sido leídos, para luego saber si hay igual cantidad de 1.
• Una forma de hacerlo es agregar al AF una memoria de PILA (LIFO: último en entrar, primero en salir) para que almacene los 0 leídos y luego las quite con cada 1 leído.
• Una memoria de pila se maneja con:
  • Poner(símbolo)
  • Símbolo=Sacar [lectura destructiva]
  • Ver si Está Vacía() Poner Sacar # Fondo de Pila

AUTÓMATAS CON PILA: AP

Autómata Finito al que se agrega memoria de PILA o LIFO (last in - first out). Reconoce Lenguaje generado por la gramática tipo 2 Independiente de Contexto (lenguajes de programación) Aumenta la capacidad de resolver problemas por el hecho de poder memorizar total o parcialmente la cadena

M.A.Paz Menvielle 2k3-2k11

AUTÓMATA CON PILA (AP) - MODELO FORMAL

AP = (2, I, Q, q0, #, A, f) donde: E = alfabeto de símbolos de entrada T = alfabeto de símbolos de pila (distinto de E) Q = conjunto finito y no vacío de estados posibles q0 = estado inicial. q0€ Q # = símbolo de referencia de pila. # e Ty # ¿ ¿ A = conjunto de estados de aceptación. AcQ f = función de transición, se distingue según sea APD f: Qx ExT- QxT* APND f: Q x (_ U {}}) xT ->P(QxT*)

M.A.Paz Menvielle 2k3-2k11

AUTÓMATA CON PILA NO DETERMINISTA - MODELO FORMAL

APND = (2, I, Q, q0, #, A, f) f: Q x (_ U {}) xT -> P(Q xT*) DIGRAFO e2, P2 / B1 90 qm f(q0, e2, p2) = { (qm, B1 ) } Σ λ e1 €2 en > qo, P1 ... ... ... ... > 90, P2 ... { (qm,₿1) } ... ... Qx T Estado de aceptación *qp Pk ... ... ... ... qa

M.A.Paz Menvielle 2k3-2k11 q0 ... ... ... ... Estado Inicial f

AUTÓMATA CON PILA NO DETERMINISTA - MODELO FORMAL

Iniciando el funcionamiento en el estado inicial q0 , y con la pila vacía marcada por #, el autómata: 1- Lee un símbolo leído de la cinta de entrada lec=eleido o no lee lec=X 2-Saca un símbolo que lee de la pila (lectura destructiva) w=sacar( 3- Transita a uno a más estados y realiza una acción sobre la pila: grabar uno o más símbolos / no grabar (se representa con 2) f(qactual, lec, w) = {(q1, B1), (q2, B2), ... , (qm, Bim)} 4- Repite los pasos 1 a 3 en forma no determinística hasta finalizar la lectura de la cadena. 5- Decide si acepta o rechaza la cadena leída. AUTÓMATA - NO DETERMINISTA - RECONOCEDOR

M.A.Paz Menvielle 2k3-2k11

APND - MODELO FORMAL: FUNCIONAMIENTO NO DETERMINISTA

APND =(2, I, Q, q0, #, A, f) con f: Q x (_ U {}}) x T -> P(Q xT*) a) El AP puede leer un símbolo de entrada o no leer, por lo que puede realizar transiciones espontáneas (2 ). b) El rango de la función de transición es P(Q x *), por lo que puede transitar a varios estados, c) Podría realizar sobre la pila una de varias acciones: 1. Desapilar: extrae un símbolo w y no almacena nada 2. f(p, a, w) = {(q,1) } no graba nada 2. Apilar: extrae un símbolo w y lo devuelve con algo más wB. f(p, a, w) = { (q, w B) } con ßer+ 3. Cambiar: extrae un símbolo w y almacena algo más B. f(p, a, w) = { (q, B) } con ßer+

M.A.Paz Menvielle 2k3-2k11

APD: EJEMPLO

Diseñar un AP que reconozca el siguiente lenguaje: L={1"On / n>= 1} GRAFO Σε, Γ/ Γ 0, 1 /1 1, # / # 1 0,1 p 1,1/11 q λ, #/# ΑΡ = ( Σ, Q, q0, #, A, f) , r PILA a=1100 1 f: Qx EXT->QxT* f(p, 1, #) = (p,# 1) f(p, 1, 1) = (p, 11) f(p, 0,1)=(q, 2) f(q, 0, 1) = (q,1) f(q, 1, #) = (r, #) f 0 1 λ >>p,# {p,#1} # >>p,1 {q, λ} {p,11} Q, T q,1 {q, λ} q,# {r,#}

M.A.Paz Menvielle 2k3-2k11 1 Σ 1 # AP = ({0, 1}, {1, #}, {p, q, r}, p, #, {r}, f)

AUTÓMATA CON PILA: MODELO MECÁNICO

APND = (E, I, Q, q0, #, A, f ) con f : Qx ({}}) xT->P(QxT*) Cinta de Entrada f(q), a, #) = { (q2, #XY ) } a b c d e f g h i . .. f Y qn q1 ... q2 X # q3 … q4 1. Lee un símbolo de entrada. 2. Saca un símbolo de la cima de pila 3. Almacena en la pila una cadena de símbolos de pila y 4. Transita a un nuevo estado. Al terminar de leer la cadena de entrada DECIDIRÁ si la acepta.

AUTÓMATA CON PILA DETERMINISTA (APD)

f = función de transición. f: Q x _ x T -> QxT* donde: T *= T U {} Un AP con transiciones À es un APND pero si cumple la condición que no exista la misma transición para otra entrada, se estará comportando como APD, así: f: Qx (_ U {}}) xT-QxT* Si ] f(q, 1, b) para qeQ y bel, entonces X f(q, a, b) Vae _

M.A.Paz Menvielle 2k3-2k11

AUTÓMATA CON PILA (APD)

f: Q x ( U {}) xT->P(QxT*), donde: *= T U {} A, b/ cc q r b / cc If(q, 1, b)| =1 y f(q, a, b) = + para q, reQ, ber, ae_ - q cualquier estado - ) Cadena leída completa o No se lee entrada - Sólo una transición - q cualquier estado - a Símbolo leído - No existe esa transición4

M.A.Paz Menvielle 2k3-2k11

AUTÓMATA CON PILA (APND)

Función de transición. f: Q x (_ U {}) x T -> P(Q xT*) Donde: r *= T U &} Condiciones que lo hacen No Determinista: a) Operar sin leer la cadena de entrada (transición 2) b) Varias opciones de Estado-Entrada-Pila a Estado-Carga de Pila P(Q x *) c) Combinación de las anteriores

M.A.Paz Menvielle 2k3-2k11

AUTÓMATA CON PILA (APND)

f: Q x ( U {}) xT -> P(Q xl*), donde: r *= T U {} A, b/ cc q r a , b / cc f(q,1, b)++ y f(q, a, b) + + para q, reQ, ber,a=> I - q cualquier estado - ) Cadena leída completa o No se lee entrada - Existe esa transición - q cualquier estado - a Símbolo leído - Existe esa transición

M.A.Paz Menvielle 2k3-2k11

AP: CONFIGURACIÓN O DESCRIPCIÓN INSTANTÁNEA

• Descripción instantánea o Configuración: Kt = (q, B, a) con: t es intervalo de tiempo, q e Q es estado actual, B E _ es sub-cadena por leer, a contenido de la pila.
• Configuración inicial: Ko = (q0, a, #) con: t=0, q0 € Q es estado inicial, a e _ es cadena por leer, # símbolo tope de pila.
• Configuración Final: Kn = (qn, A, a) con: t=n, q, es estado actual, A es cadena leída completa, a contenido de la pila.
• Configuración de Aceptación: Kn = (q1, 1, #) Si qn E A y # es símbolo de tope de pila. A es cadena leída completa

AP: MOVIMIENTO

• Tránsito o movimiento de una configuración a otra. Si existe la transición f(p, a, b) = (q, ba) Estado símbolo saca de prox. escribe Actual leído la pila estado en la pila
• El movimiento de p a q se representa: (p, aß, b) + (q, , ba) p= estado actual, a= símbolo leído, ß=sub-cadena que resta por leer, b =símbolos que se saca de la pila, q=próximo estado, ba=escribe en la pila

M.A.Paz Menvielle 2k3-2k11

AP: MOVIMIENTO GENERALIZADO DE CONFIGURACIÓN INICIAL A ACEPTACIÓN

• Movimiento Generalizado: movimiento de una configuración a otra en uno o mas pasos: (q, α, β) +* (p, μ, 0) Significa: (q, a, B) + (q1, a1, B1) + (q2, a2, B2) | ... I (p, u, d) - qi € Q, a¡ es cadena por leer, - ¡¡ contenido de la pila - F* indica cantidad finita de movimientos.
• Movimiento Gen. de Config. inicial a Config de Aceptación: (q0, a, #) +* (qn, , d) , con - q0 € Q y a es cadena por leer, - qn € A, À significa que no queda nada por leer, - F* indica cantidad finita de movimientos.

AP: ACEPTACIÓN DE LENGUAJES

AP acepta cadenas que han sido completamente leídas y transitan desde su configuración inicial a final. De 3 formas: a) Aceptación por pila vacía: 1, # / # L(AP)={a / (q0, a, #) F* (qn, 2, #) con qn, q0 € Q, #E T, aez* , qn¢ A} b) Aceptación por estado final: λ, Ο / λ L(AP)={a / (q0, a, #) +* (qn, 2, 0) con qn, q0 € Q, #E I, aez* , que A, 0 € T+, ô contenido de la pila} c) Aceptación por pila vacía y estado final: 2, # / # L(AP)={a / (q0, a, #) +* (qn, 2, #) con qn, q0 € Q, #E I, aez* , que A}

M.A.Paz Menvielle 2k3-2k11

APD: EJEMPLO DE RECONOCIMIENTO DE LENGUAJE

Diseñar un AP que reconozca el siguiente lenguaje: L={1"On / n>= 1} GRAFO Σε, Γ/ Γ 0, 1 /1 1, # / # 1 0,1 p 1,1/11 q λ, #/# ΑΡ = ( Σ, Q, q0, #, A, f) , r PILA a=1100 1 f: Qx ExT-QxT* f(p, 1, #) =(p,# 1) f(p, 1, 1) = (p, 11) f(p, 0,1)=(q, 2) f(q, 0, 1) = (q, 2) f(q, 1, #) = (r, #) f 0 1 λ ->p,# p,#1 -p,1 α, λ p,11 Q, r q,1 α, λ q,# r,#

M.A.Paz Menvielle 2k3-2k11 1 1 # # AP = ({0, 1}, {1, #}, {p, q, r}, p, #, {r}, f)

DISEÑO DE UN APD: EJEMPLO-1

Diseñar un AP que reconozca el siguiente lenguaje: L={1^0^ / n>= 1} GRAFO 1 0, 1 /1 1, # / # 1 0, 1 /2 p 1,1 / 11 q AP = ({0, 1}, {1, #}, {p, q, r}, p, #, {r}, f) 0,#/# r Árbol de descripciones instantáneas a=1100 (p, 1100, #) (Q, B, I) Movimiento o tránsito (p, 100, # 1) (p, 00,#11) + (q,0,#1) (p, 00, #11) (q, 0, #1) Movimiento Gen. de Conf. Inicial a Conf. Final V (q, λ, #) -> (r, À, #)

M.A.Paz Menvielle 2k3-2k11 (p,1100,#) +* (r,),#)

DISEÑO DE UN APD: EJEMPLO-2

Diseñar un AP que reconozca el siguiente lenguaje formal (Análisis Sintáctico) letra = input("Ingrese una letra: ") if letra == 'a' : a b c print ("letra a") d e else : fc print ("otra letra' d e AP = ({a, b, c, d, e, f}, {a, d, f, #}, {p, q, r, s, t, u, v, w, z}, p, #, {z}, f) a= abcdefcde b, a / a c, a / a Ce > q r a, # / # a d, a / ad e, d / z C s λ, α / λ f, a / f λ, #/# t c, f / f w e, d /1 d, 1 / d v u d, f / d

M.A.Paz Menvielle 2k3-2k11

DISEÑO DE UN APND: EJEMPLO-3

Reconoce lenguaje cuyas cadenas son palíndromos de largo par. B=ZZ-1 donde Z={a, b}* CP b, b /2 a, a /1 q A,#/# r AP = ({a, b}, {a, b, #}, {p, q, r}, p, #, {r}, f) a, # / # a b, # / # b b, b /2 a, a /1 a, a / aa b, b / bb a, b / ba f a b λ >>p,# {p, #a} {p,#b} -p, a {(p, aa),(q, 1)} {p, ab} Q, T ->p, b {p, ba} {(p, bb), (q, 2)} q, # {r,#} q, a {q, λ} q, b {α, λ} Σ b, a / ab

M.A.Paz Menvielle 2k3-2k11

DISEÑO DE UN APND: EJEMPLO-3 (PALÍNDROMOS)

Reconoce lenguaje cuyas cadenas son palíndromos de largo par. B=ZZ-1 donde Z={a, b)* C p b, b /2 a, a /X λ, #/# q r AP = ({a, b}, {a, b, #}, {p, q, r}, p, #, {r}, f) Árbol de descripciones instantáneas (p, abba, #) a, a / aa b, b / bb a=abba a, b / ba b, a / ab (p, bba, # a) (p, ba, #ab) b, b /1 0 b, b / bb Movimiento o tránsito (q, a, #a) + (q, λ, #) (p, a, #abb) (q, a, #a) Mov. Gen. de Conf. Inicial a Conf. Final (p, 1, #abba) (q, λ , #) - (p, abba, #) +* (r, ), #) V X (r, λ , #)

M.A.Paz Menvielle 2k3-2k11 a, # / # a b, b /2 a, a /1 b, # / # b