Autómatas de PilaJesús E. Carpio 14-0807Juan A. Ramírez 13-1072

Autómata de Pila

• 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.

• El lenguaje que reconoce un autómata con pila

pertenece al grupo de los lenguajes libres de

contexto en la clasificación de la Jerarquía de

Chomsky.

Definición formalUn Autómata a Pila se define como la séptupla:(Σ, P, Q, A0, q0, f, F)donde:

• Σ: alfabeto de entrada.• P: alfabeto de la pila.• Q: conjunto de estados.• A0: símbolo inicial de la pila (#).• q0: símbolo inicial del conjunto de estados.• f: función de transición. Es una aplicación de• Q x Σ {λ} x P en el conjunto de partes de P(QxP)*.• F: conjunto de estados finales o de aceptación.

Diagrama de transiciónUn diagrama de transición (Función de transición) modela el comportamiento del autómata. Es una aplicación de QxΣ∪{λ}xP en el conjunto de partes de P(QxP)*. Pudiendo interpretarlo de la siguiente forma: f(q, a, A) = {(q1,Z1),…, (qn, Zn)} : Si el AP se en encuentra en el estado q, lee el símbolo a de la cinta de entrada, y aparece el símbolo A en el tope de la pila, pasará al estado qi (n≥i≥1), borrará el símbolo A de la pila e introducirá la palabra Zi, situando la cabecera de la misma en el tope de la pila, y avanzando una posición en la cinta de entrada.

f(q, λ, A) = {(q1,Z1),..., (qn,Zn)}: Si el AP se encuentra en el estado q y aparece el símbolo A en el tope de la pila, pasará al estado qi (n≥i≥1), borrará el símbolo A de la pila e introducirá la palabra Zi, situando la cabecera de la misma en el tope de la pila, y mantendrá la misma posición en la cinta de entrada.

Autómata de Pila Determinista

Un AP es Determinístico si verifica:1. ∀q∈Q, ∀A∈P, cardinal(f(q, λ, A)) 0⇒f(q, a, A) =∅,

∀a∈Σ.2. ∀q∈Q,∀A∈P,∀a∈Σ∪{λ} ⇒cardinal(f(q, a, A))<2.

Lenguaje aceptado por un autómata con pila.

Lenguaje aceptado por un AP (M=(Σ, P, Q, A0, q0, f, F)• Lenguaje aceptado por criterio de estado finalLEF(M) = (x / (q0, x, A0) →* (p, λ, X), p∈F, X∈P*}• Lenguaje aceptado por criterio de pila vacíaLPV(M) = (x / (q0, x, A0) →* (p, λ, λ), p∈Q}

Ejemplo: Autómata con pila que reconoce el lenguaje L={xnym, n>m} • Aplicamos el algoritmo de LEF⇒LPV

Autómatas finitos con pila no-deterministas (AFPND)

• Un autómata finito con pila no-determinista (AFPND) es una séptupla donde:

Es decir, el comportamiento del autómata depende en cada transición

• del estado actual

• posiblemente del siguiente símbolo de la entrada

• del símbolo en la cima de la pila

Y se modifica el autómata en el sentido que

• se cambia (posiblemente) del estado

• se consume (posiblemente) el siguiente símbolo de la entrada

• se modifica (posiblemente) el contenido de la cima de la pila.

Generalidades

q1 q2

q 3q4

a /z/A H

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/za /z/AHB

Q u ita r C o lo ca r

z

Ejemplo

q1 q2

q 3q4

a /z/AH

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/z

a /z/AHB z

¿Acepta aab?

¿Acepta aab?

q1 q2

q 3q4

a /z/A H

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/z

a /z/AHB

z

¿Acepta aab?

a /z/AH a /A /a b /b /bq 2q 1 q 2

q 1

z

a)

¿Acepta aab?

a /z/AH a /A /a b /b /bq 2q 1 q 2q 1

z

a)

HA

¿Acepta aab?

a /z/AH a /A /a b /b /bq 2q 1 q 2

q 1

z

a)

HA

Ha

¿Acepta aab?

a /z/AH a /A /a b /b /bq 2q 1 q 2

q 1

z

a)

HA

Ha Falló

¿Acepta aab?

q1 q2

q 3q4

a /z/A H

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/z

a /z/AHB

z

b)

¿Acepta aab?

a /z/z a /z/z b /F /a Ha Eq 3q 2 q 4q 1

z

b)

¿Acepta aab?

a /z/z a /z/z b /F /a Ha Eq 3q 2 q 4q 1

z

b)

z

¿Acepta aab?

a /z/z a /z/z b /F /a Ha Eq 3q 2 q 4q 1

z

b)

z z

¿Acepta aab?

a /z/z a /z/z b /F /a Ha Eq 3q 2 q 4q 1

z

b)

z z

Falló

¿Acepta aab?

q1 q2

q 3q4

a /z/AH

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/za /z/AHB

z

c)

¿Acepta aab?

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

z

c)

¿Acepta aab?

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

z

c)

BHA

¿Acepta aab?

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

z

c)

BHA

BHbF

¿Acepta aab?

a /z/A HB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

z

c)

BHA

BHbF

BHbEaHa

¿Acepta aab?

a /z/A HB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

z

c)

BHA

BHbF

BHbEaHa

El autómata acepta aab

q1 q2

q 3q4

a /z/AH

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/z

a /z/AHB z

¿Acepta ab?

q1 q2

q 3q4

a /z/A H

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/z

a /z/AHB z

¿Acepta ab? No

q1 q2

q 3q4

a /z/AH

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/z

a /z/AHB z

¿Acepta aba?

q1 q2

q 3q4

a /z/AH

a /A /ab /b /b

a /z/z

a /A /F bb /F /a Ha E

a /z/z

a /z/AHB z

¿Acepta aba? No

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z)

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/A HB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( , , )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, , )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB)

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/A HB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB) ├── ( , , )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, , )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/A HB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/A HB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB)

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB) ├── ( , , )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB) ├── ( q4, , )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/A HB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB) ├── ( q4, ε, )

Descripción instantánea

z

BH

A

BHbF

BHbE

aH

a

a /z/AHB a /A /F b b /F /a Ha Eq 3q 3 q 4q 1

( q1, aab, z) ├── ( q3, ab, AHB) ├── ( q3, b, FbHB) ├── ( q4, ε, aHaEbHB)

Aplicaciones que requieren análisis sintáctico

• Compilador para un computador de automatización industrial

• Herramienta de consulta de bases de datos distribuidas

• Creación de un motor de base de datos relacional

• Creación de un motor de base de datos OO (Base de objetos) y su lenguaje

de consulta (OQL)

• Simulador robótico con lenguaje de programación para robots

• Generador de analizador sintáctico (YACC, JAVACC)

Referencias• Autómatas de Pila: Transiciones - Universidad de

Cantabria - http://www.slideshare.net/rihardjancomartinez/3-7-transiciones?qid=c05abe18-18f5-4105-889c-549d052d50a9&v=&b=&from_search=2

• http://www.uhu.es/francisco.moreno/talf/docs/tema7.pdf

• Dean Kelly, Teoría de Autómatas y lenguajes Formales.