Automatas
M = (Q, A, d, q0, F)
Q: Conjunto de Estados (finito)
A: Alfabeto.
d: Q x A ® Q: Funcion de un (Estado, Simbolo) a Estado.
q0Î Q: Estado Inicial.
FÍ Q: Conjunto de Estdados de Aceptacion.
Extension de d: d*: Q x A* ® Q
M = (Q, A, d, q0, F)
Q: Conjunto de Estados (finito)
A: Alfabeto.
d Í Q x A x Q: Funcion de un (Estado, Simbolo) a Estado.
q0Î Q: Estado Inicial.
FÍ Q: Conjunto de Estdados de Aceptacion.
M = (Q, A, d, q0, F, V)
Q: Conjunto de Estados (finito)
A: Alfabeto.
d Í Q x A x Q: Relacion de (Estados, Simbolo, Estado).
q0Î Q: Estado Inicial.
FÍ Q: Conjunto de Estdados de Aceptacion.
VÍ Q x Q: Relacion de transicion l
M = (Q, AE, AP, d, q0, z0, F)
Q: Conjunto de Estados (finito)
AE: Alfabeto de Entrada.
AP: Alfabeto de Pila.
d: Q x (AE È {l}) x (AP È {l}) ® Subconjuntos Finitos de Q x AP*:
Funcion de un (Estado, Simbolo) a Estado.
q0Î Q: Estado Inicial.
z0Î AP: Simbolo Inicial de la Pila.
FÍ Q: Conjunto de Estados de Aceptacion.
Restricciones Automata de Pila Deterministico
I. Para cada q Î Q y z Î AP , cuando (q, l,Z) es no vacio, entonces d(q,a,Z) es vacio para todo a Î AE.
II. Para ningun q Î Q, z Î AP y a Î AE È {l}, d(q,a,Z) contiene mas de un elemento.
Descripcion Instantanea:
(q,a,b) Î Q x AE* x AP*
M = (Q, AE, AC,
d,
q0, b, F)
Q: Conjunto de Estados (finito)
AE:
Alfabeto de Entrada (AC
- b).
AC: Alfabeto de Cinta.
d: Q x AC ® Q x AC x {L, R, N}: Funcion de un (Estado, Simbolo) a Estado
(En el libro de Hopcroft no aparece N).
q0Î Q: Estado Inicial.
bÎ
AC:
Blanco en la Cinta.
FÍ Q: Conjunto de Estdados de Aceptacion.
Descripcion Instantanea
(a,q,b) Î AC* x Q x AC*