Automatas_de_pila_Completo
Páginas: 7 (1564 palabras)
Publicado: 9 de noviembre de 2015
Teoría de la
Computación
M. en I. Jorge Carlos Reyes Magaña
Pila
◦ Último en entrar primero en salir
Solamente se puede introducir
por el tope de la pila
1
06/05/2013
Recordemos que los Autómatas Finitos no
son lo suficientemente poderosos para
aceptar los Lenguajes libres de contexto.
Autómatas de pila
◦ Tienen la estructura de un AF: estados y
transiciones.
q0
q1Los elementos en las transiciones cambian
Transiciones en Autómatas de Pila.
Se registran los caracteres de entrada y los movimientos de la pila.
ω/α/β
q1
Ahora las transiciones tienen 3 partes:
1. ω = Entrada (elemento de la cadena a ser parseado)
2. α = Sale de la pila
3. β = Entra a la pila
Primero se ejecuta la operación de sacar de la pila y luego de meter
2
06/05/2013
Paradiseñar un AP se tiene que repartir lo
que se requiere ser “recordado” entre los
estados y la pila.
Distintos diseños para un mismo problema
pueden tomar decisiones diferentes en
cuanto a qué recuerda cada cual.
Ejemplo: Diseñar un AP que acepte
exactamente el lenguaje con palabras de la
forma anbn, para cualquier número natural.
◦ Ejemplo usando un contador
a//a
b/a/
q
6
3
06/05/2013cadena/ Saca/ Entra
Traza de ejecución para w = aabb
Estado
q
q
q
q
q
Por leer
aabb
abb
bb
b
ε
Pila
Vacía
a
aa
a
Vacía
a/ /a
b/a/
q
7
Problema!!!
◦ El AP también acepta palabras como abab
(corroborar con la traza de ejecución).
◦ El AP no tiene la forma deseada: anbn
◦ No se ha recordado cuando se terminan las a’s e
inician las b’s.
Solución
◦ Utilizar los estados paramemorizar las situaciones
de estar consumiendo a’s o estar consumiendo b’s.
8
4
06/05/2013
anbn
cadena/ Saca/ Entra
b/a/
a//a
b/ a/
q0
q1
Ejemplo:
aaabbb
aaabbb
aaabbb
aaabbb
aaabbb
La pila esta vacía
y se llega a un
estado aceptado
(q1), por lo tanto
la palabra se
acepta
aaabbb
a
a
a
a
a
a
a
a
a
q0
q0
q0
q1
q1
q1
Ejemplo: Proponer un AP para el lenguaje delos palíndromos con número par de símbolos
en {a,b}, esto es, palabras que se leen igual de
izquierda a derecha y viceversa, y por lo tanto
tienen la forma wwR donde wR es el reverso de
w (invertir el orden).
Ejemplos:
¿Cual sería la estrategia a seguir?
◦ abba, aa, bbbbbb
◦ aab, aabaa
(correctos)
(incorrectos)
10
5
06/05/2013
cadena/ Saca/ Entra
Estrategia:
◦ Almacenar en la pilala primera mitad de la
palabra y luego ir comparándola letra por
letra contra la segunda mitad.
a/ /a
b/ /b
s
//
b/b/
a/a/
f
11
Consideraciones:
◦ La presencia de una transición de s a f, en que ni se
consumen caracteres de la entrada, ni se manipula
la pila.
◦ ¿Se puede llegar a un estado final sin recorrer la
mitad de la palabra?
◦ ¿Cómo saber que ya llegamos exactamente ala
mitad de la palabra?
12
6
06/05/2013
En un AFN una palabra es aceptada cuando
existe un cálculo que permite aceptarla,
independientemente de que un cálculo en
particular se vaya por el camino erróneo.
Lo importante es que exista un cálculo que
acepte la palabra en cuestión.
13
cadena/ Saca/ Entra
a/ /a
s
b/b/
b/ /b
//
a/a/
f
Traza de ejecución para w = abbaEstado
s
s
s
f
f
F
Por leer
Pila
abba
bba
ba
ba
a
Pila vacía
a
ba
ba
a
Pila vacía
14
7
06/05/2013
Se pueden aplicar métodos de combinación
modular de autómatas, como se realizaron
con los AF.
Dados dos AP M1 y M2 y que aceptan los
lenguajes L1 y L2 respectivamente, se puede
obtener un AP que acepte la unión L1 U L2
introduciendo un nuevo estado inicial s0 con
transiciones / / a losdos antiguos
estados iniciales de M1 y M2.
15
Un AP es un séxtuplo (K, Σ, Γ, Δ, s,
F) donde:
◦
◦
◦
◦
◦
◦
K es un conjunto de estados
Σ es el alfabeto de entrada
Γ es el alfabeto de la pila
. ( K x* x * ) x( K x * )
s Є K es el estado inicial
. F K
16
8
06/05/2013
Si se tiene una transición de la forma
((p,u,β),(q,γ)) Є Δ:
◦
◦
◦
◦
Estando en el estado p, consume u de...
Leer documento completo
Regístrate para leer el documento completo.