Automatas de pila

1. Índice
2. Introducción 4
2.1. ¿Qué es un autómata con pila? 4
2.2. ¿Qué es una máquina de Turing? 6
3. Características de los autómatas con pilas 7
3.1. Autómata de pila determinista 7
3.2. Autómata de pila no determinista 7
4. Características de las máquinas de Turing 9
Máquina de Turing de una cinta determinista 9
Funcionamiento M.T. de una cinta determinista 9
Máquina de Turing deuna cinta no determinista 11
Funcionamiento M.T. de una cinta no determinista 11
Máquina de Turing de n cinta 12
Funcionamiento M.T. de n cintas 12
5. Lenguajes aceptados por los autómatas de pila y máquinas de Turing 14
5.1. Autómatas de pilas 14
5.2. Máquina de Turing 15
6. Funcionamiento aplicación práctica de autómata de pila 16
7. Funcionamiento aplicación práctica de máquina deTuring 17
8. Conclusiones orientadas al uso y aplicación de los autómatas de pilas y máquina de Turing 20
8.1. Autómatas de pilas 20
8.2. Máquina de Turing 20
9. Conclusión 21
10. Bibliografía y linkografia 22
10.1. Bibliografía 22
10.2. Linkografía 22

 
2. Introducción
En este informe conoceremos los conceptos, características, lenguajes aceptados, ejemplos, usos, importancia yaplicaciones de los autómatas de pilas y máquina de Turing.

2.1. ¿Qué es un autómata con pila?
Un autómata de pila se puede considerar una máquina abstracta (autómata) que mantiene el control sobre una cinta de entrada de sólo lectura y un almacenamiento de datos con acceso de tipo pila.

Ilustración 1- Un autómata a pila es esencialmente un autómata finito con una estructura de datos de pilaSegún Hopcroft, el autómata a pila sólo puede acceder a la información disponible en su pila de acuerdo con la forma de manipular una pila FIFO (first-in-first-out way, primero en entrar primero en salir).
Además añade, se puede interpretar una autómata a pila como el dispositivo mostrado en la Ilustración 1. Un “control de estados finito” lee las entradas, un símbolo cada vez. El autómata a pilapuede observar el símbolo colocado en la parte superior de la pila y llevar a cabo su transición basándose en el estado actual, el símbolo de entrada y el símbolo que hay en la parte superior de la pila. Alternativamente, puede hacer una transición “espontánea”, utilizando ε como entrada en lugar de un símbolo de entrada.
Según Kelley, el autómata con pila en todo momento se encuentran en unestado y el cambio de estado depende del estado actual y de una información adicional, donde se incluyen el símbolo de entrada actual y el símbolo que está en ese momento en la cima de la pila. Además de cambiar de estado, el autómata de pila cambia, también, la cima de la pila.
 
2.2. ¿Qué es una máquina de Turing?
La máquina de Turing es un dispositivo teórico muy simple pero con una grancapacidad computacional, es decir, permite resolver problemas de una gran complejidad.
La M.T. es un modelo matemático para representar a una maquina teórica. A pesar de su simplicidad la M.T. tiene el mismo poder computacional que una computadora de propósito general.
La M.T. es interesante, sobre todo, por el conjunto de lenguajes que permite reconocer y también generar y por el conjunto de funcionesque puede computar.
La máquina de Turing es un programa con instrucciones y bucles estructurados, que permite leer, escribir o buscar en una cinta.




 
3. Características de los autómatas con pilas
3.1. Autómata de pila determinista
Para calificar a un autómata con pila como determinista se deben dar dos circunstancias; primero, que en la definición de cada componente de la función detransición existan un único elemento lo que da la naturaleza determinista. Además puede darse la circunstancia de que el autómata esté en el estado s y en la pila aparezca el símbolo sZ, entonces, si existe una definición de transición posible para algún símbolo cualquiera a del alfabeto de entrada, pero, además existe otra alternativa para la palabra vacía ℮, también esto es una forma de...