PDF de programación - Autómatas de pila

Autómatas de pila

Introducción

- Los autómatas finitos deterministas / no deterministas,

tienen un poder de expresión muy grande para
reconocer lenguajes

- Sin embargo, también tienen fuertes limitantes:

- No pueden reconocer expresiones compuestas, que definan

una sintaxis de combinación de símbolos con diferentes
jerarquías

- Por ejemplo: lenguaje definido por las expresiones matemáticas

definidas sobre los números binarios (+,-,*, /), permitiendo su
agrupamiento con los símbolos “(” y “)”

Autómatas de pila

- Los autómatas finitos de pila son una extensión de los

autómatas finitos deterministas:

- Mantienen un conjunto de estados y transiciones entre

estados, considerando un alfabeto de entrada

- Incorporan una pila, que les permite recordar que símbolos
han procesado previamente, para tomar decisiones a futuro

Definición Formal

- Un autómata de pila determinista se define como la

, G

, d

, q0, g 0, F), donde:

, alfabeto de entrada
, alfabeto de pila
: D ˝ Q x G x (S
: D ˝ Q x G x (S

séptupla A = (Q, S
- Q, conjunto finito de estados
- S
- G
- d
- q0 ˛ Q: estado inicial
- g 0 ˛
- F ˝ Q, conjunto de estados finales del autómata

: símbolo inicial de la pila

{l })  Q x G *
{l })  Q x G *

d
¨
¨
G
Ejemplo

- Considere el problema de diseñar un autómata que

acepte expresiones matemáticas sobre números binarios,
y acepte los paréntesis para agrupar operaciones. Las
expresiones deben de finalizar con el símbolo

Ejemplo

Ejemplo