Automatas De Pilas
Páginas: 3 (707 palabras)
Publicado: 7 de noviembre de 2012
UNIVERSIDAD NACIONAL AUTONOMA DE NICARAGUA.
UNAN- Managua.
FACULTAD REGIONAL MULTISCIPLINARIA DE CARAZO.
FAREM- Carazo.
TRABAJO DE:
“TEORIA COMPUTACIONAL.”
DOCENTE: Msc.ConcepcionMendieta.
JINOTEPE, 30 DE OCTUBRE DEL 2012
Autómata de Pila.
* SE DEFINE
Un autómata de pila formalmente como una séxtupla de la forma (Z, V, P, delta, O, F); donde:
Z= Conjunto finitos deestados.
V= Alfabeto de la maquina.
P= Conjunto finito de símbolos de pila.
Delta= Colección finita de transiciones.
O= Estado Final o Inicial.
F= Conjunto de estados de aceptación.
*ESQUEMATICAMENTE:
0
1
2
3
4
5
Cabeza lectora
Dirección del movimiento de la cabeza
MECANISMO DE CONTROL.
El autómata de pila analiza cadenas de la misma manera que los autómatas finitos.La diferencia con ellos es que el símbolo leído, X, tenía en cuenta el estado de la maquina A, donde se encontraba y la función de transición ubicada en el par ordenado (A,X) dándonos así eldestino del nuevo estado B. Usando el correspondiente GRAFO, la transición se manifiesta como:
B
A
X
En cambio; la transición de los autómatas de pila se representa:
B
A[X, C, D]
“A” es el estado de origen donde se encuentra la maquina. Si la tira en la celda, señala por la cabeza lectora tiene el símbolo al X, lee lo que tiene la pila en su cabezalectora con la pila vacía.
Lo importante es el agregado de los autómatas finitos de un sistema de memorias internas en forma de pila con lo que se incrementa considerablemente el potencial deprocesamiento de lenguaje del autómata.
1
2
3
&, &, #
&, #, &
Y, X, &
Y, X, &
X, &, X
Ejemplo de un autómata a pila que justamente reconoce laspalabras del lenguaje (XnYn/n es N) para el cálculo no existe autómata finito que lo reconociera.
El estado “O” es el inicio.
El estado “3” es la aceptación.
En conclusión, se entiende que se...
UNAN- Managua.
FACULTAD REGIONAL MULTISCIPLINARIA DE CARAZO.
FAREM- Carazo.
TRABAJO DE:
“TEORIA COMPUTACIONAL.”
DOCENTE: Msc.ConcepcionMendieta.
JINOTEPE, 30 DE OCTUBRE DEL 2012
Autómata de Pila.
* SE DEFINE
Un autómata de pila formalmente como una séxtupla de la forma (Z, V, P, delta, O, F); donde:
Z= Conjunto finitos deestados.
V= Alfabeto de la maquina.
P= Conjunto finito de símbolos de pila.
Delta= Colección finita de transiciones.
O= Estado Final o Inicial.
F= Conjunto de estados de aceptación.
*ESQUEMATICAMENTE:
0
1
2
3
4
5
Cabeza lectora
Dirección del movimiento de la cabeza
MECANISMO DE CONTROL.
El autómata de pila analiza cadenas de la misma manera que los autómatas finitos.La diferencia con ellos es que el símbolo leído, X, tenía en cuenta el estado de la maquina A, donde se encontraba y la función de transición ubicada en el par ordenado (A,X) dándonos así eldestino del nuevo estado B. Usando el correspondiente GRAFO, la transición se manifiesta como:
B
A
X
En cambio; la transición de los autómatas de pila se representa:
B
A[X, C, D]
“A” es el estado de origen donde se encuentra la maquina. Si la tira en la celda, señala por la cabeza lectora tiene el símbolo al X, lee lo que tiene la pila en su cabezalectora con la pila vacía.
Lo importante es el agregado de los autómatas finitos de un sistema de memorias internas en forma de pila con lo que se incrementa considerablemente el potencial deprocesamiento de lenguaje del autómata.
1
2
3
&, &, #
&, #, &
Y, X, &
Y, X, &
X, &, X
Ejemplo de un autómata a pila que justamente reconoce laspalabras del lenguaje (XnYn/n es N) para el cálculo no existe autómata finito que lo reconociera.
El estado “O” es el inicio.
El estado “3” es la aceptación.
En conclusión, se entiende que se...
Leer documento completo
Regístrate para leer el documento completo.