Clase 17: Autómatas de pila Solicitado: Ejercicios 14: Autómatas de pila de GLC M. en C. Edgardo Adrián Franco Martínez http://computacion.cs.cinvestav.mx/~efranco @efranco_escom

[email protected]

1

• Autómata de pila • Definición formal de autómata de pila • Configuración de un autómata de pila • Movimiento de un autómata de pila • Restricciones de un autómata de pila • Operaciones elementales de un autómata de pila

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

Contenido

• Ejemplo 01 • Lenguaje reconocido por un autómata de pila • Teorema 1 • Teorema 2

• Conversión de GLC a AP • Ejercicios 14: Autómatas de pila de GLC Compiladores (Lenguajes y gramáticas - Edgardo A. Franco)

2

• El lenguaje que reconoce un autómata de pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la Jerarquía de Chomsky. • Un autómata de pila es esencialmente un autómata finito que posee control sobre un cinta y una pila del tipo LIFO.

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Un autómata de pila es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

3

• • • •

Q: Es el conjunto finito de estados. Σ: Es el alfabeto de entrada, es finito. Γ: Es el alfabeto de pila. δ: Es la función de transición, y es una aplicación de la forma : δ : Q × {Σ ∪{λ}} × Γ → Q × Γ* • q0: Es el estado inicial, y cumple q0 ∈ Q. • F: Es el conjunto de estados finales, F ∈ Q.

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Un autómata de pila se puede definir formalmente como una séxtupla: R=(Q, Σ, Γ, δ, q0, F)

4

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Los autómatas de pila, en forma similar a como se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto. • Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos. • Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un número finito de estados.

5

• A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO).

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Uno de estos estados se designa como estado inicial, y algunos estados como finales.

• Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. 6

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x

7

(p, u, β)

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Se define configuración de un autómata de pila a su situación en un instante, que se puede expresar formalmente de la siguiente manera:

• p: Representa el estado actual del autómata. • u: Es la cadena de entrada que resta por analizar. • β: Es el contenido de la pila, en el instante considerado 8

δ(p, u, β) → (q, γ)

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Se entiende por movimiento de un autómata a una transición entre configuraciones, y se representa por el operador binario →.

9

de

pila

tiene

las

siguientes

• La cinta se desplaza en un sólo sentido, y su cabeza sólo puede leer.

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Un autómata restricciones:

• La pila, está limitada en un extremo por definición, cuando se lee un elemento de la pila, este desaparece o se saca, y cuando se escribe en la pila, se introduce un elemento. 10

• Dependientes de la entrada: se lee ei, y se desplaza la cinta, y en función de ei, qj (el estado en que se encuentra la cinta), y Z (el valor de la pila), el control pasa a otro estado ql, y en la pila se introduce Z’, o se extrae Z, o no se hace nada. • Independientes de la entrada: puede ocurrir lo mismo que en el caso anterior, sólo que ei no interviene, la cinta no se mueve, lo que permite manejar la pila sin las informaciones de entrada.

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Las operaciones elementales, que se pueden realizar en una autómata de pila son:

11

Q = {q0, q1}. Σ = {a, b}. Γ = {A}. q0 = {q0}. F = {q0, q1}

δ(q0, a, λ) → (q0, A) δ(q0, b, A) → (q1, λ) δ(q1, b, A) → (q1, λ)

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Autómata de pila que acepte { ai bi : i ≥ 0}

12

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico.

13

• Así como las gramáticas regulares tienen un autómata equivalente (autómata finito), las gramáticas libres de contexto tienen su contraparte en forma de maquina, es decir, un autómata de pila (AP).

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Para toda gramática libre de contexto G, existe un autómata de pila R, tal que el lenguaje generado por la gramática L(G) es reconocido por el autómata de pila R. L( G ) = L( R )

14

• De los dos teoremas anteriores se deduce que el conjunto de lenguajes reconocidos por los autómatas de pila, son los lenguajes de tipo 2 y que todo lenguaje de tipo 2 se puede reconocer por un autómata de pila.

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Para todo reconocedor constituido por un autómata de pila R, existe una gramática libre de contexto G, tal que el lenguaje reconocido por el autómata es igual al generado por la gramática L(R)=L(G)

15

R=({p, q}, VT, {VT U VN}, δ, p, {q})

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Sea G=(VT, VN, S, P) una gramática libre de contexto, su autómata de pila R seria:

• La función de transición δ se define de la siguiente manera: 1. δ(p, λ, λ) → (q, S) • Esta regla solo se usa en la primera transición. 16

• • • • •

Esta regla es para todo símbolo terminal x ∈ VT. Saca x de la pila Avanza el símbolo x de la cinta No escribe nada en la pila No cambia de estado

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

2. δ(q, x, x) → (q, λ)

3. δ(q, λ, A) → (q, α) • • • • •

Esta regla es para toda regla de producción A → α ∈ P. No avanza la cinta Saca A de la pila Mete α en la pila No cambia de estado

17

• S → aSa • S → bSb • S→c

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Obtener un autómata de pila que acepte el lenguaje generado por la gramática libre de contexto cuyas reglas son:

18

2. δ(q, a, a) → (q, λ) • δ(q, b, b) → (q, λ) • δ(q, c, c) → (q, λ)

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• La función de transición δ: 1. δ(p, λ, λ) → (q, S)

3. δ(q, λ, S) → (q, aSa) • δ(q, λ, S) → (q, bSb) • δ(q, λ, S) → (q, c) 19

Estado

Falta por leer

Pila

Transición

p

abcba

λ

δ(p, λ, λ) → (q, S)

q

abcba

S

δ(q, λ, S) → (q, aSa)

q

abcba

aSa

δ(q, a, a) → (q, λ)

q

bcba

Sa

δ(q, λ, S) → (q, bSb)

q

bcba

bSba

δ(q, b, b) → (q, λ)

q

cba

Sba

δ(q, λ, S) → (q, c)

q

cba

cba

δ(q, c, c) → (q, λ)

q

ba

ba

δ(q, b, b) → (q, λ)

q

a

a

δ(q, a, a) → (q, λ)

q

λ

λ

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

• Si se realiza la verificación de su funcionamiento con la cadena abcba se tiene:

20

• Encuentre un autómata de pila para las siguientes GLC y verifique

con al menos dos cadenas de entrada: 1.E → TE’ E’ → +TE’ E→ (E) E→ id E’→ +T T→ FT’ T→ (E) T→ id T’→ *FT’ T’→ *F F→ (T) F→ id

2.P→ iEtPabe| iEtPeP|a|Eab E→ b 3.P→ iEtPP’| a|Eab P’→ abe|eP E→ b

Teoría computacional Clase 17: Autómatas de pila Prof. Edgardo Adrián Franco Martínez

Ejercicios 14: “Autómatas de pila de GLC”

4.S → AB A → aA | a B → bB | b

*Se entregarán antes del día Domingo 03 de Noviembre de 2013 (23:59:59 hora limite). *Incluir la redacción de cada ejercicio *Portada y encabezados de pagina

21