1. Autómatas de pila
1.1. ¿Qué es?
1.1.1. Es un modelo matemático de un sistema que recibe una cadena constituida por símbolo de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.
1.2. Reconocimiento
1.2.1. El lenguaje que reconoce un autómata con pila pertenece al grupo de los lenguajes libres de contexto en la clasificación de la jerarquía de chomsky.
1.3. Funcionamiento
1.3.1. En forma similar a cómo se usan los autómatas finitos, también se pueden utilizar para aceptar cadenas de un lenguaje definido sobre un alfabeto A. Los autómatas de pila pueden aceptar lenguajes que no pueden aceptar los autómatas finitos.
1.4. Clasificación
1.4.1. Autómata con pila determinístico
1.4.1.1. Para clasificar a un autómata con pila como determinístico deben darse dos circunstancias, en primer lugar que en la definición de cada componente de la función de transición exista un único elemento lo que da la naturaleza determinista.
1.4.2. Autómata con pila no determinista
1.4.2.1. Un autómata finito con pila no determinista consta de los mismos parámetros de un AFPD.
2. Máquina de turing
2.1. ¿Qué es?
2.1.1. Es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de regla. A pesar de su simplicidad una máquina de turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una cpu dentro de un computador.
2.2. Consta de
2.2.1. Una cinta
2.2.1.1. Qué se divide en celdas, uno al lado de la otra. Cada celda contiene un símbolo de algún alfabeto finito.
2.2.2. Un cabezal
2.2.2.1. Qué puede leer y escribir símbolos en la cinta y mover la cinta a la izquierda y a la derecha una celda a la vez.
2.2.3. Un registro de estado
2.2.3.1. Que almacena el estado de la máquina de turing, uno de los estados finitos.
2.2.4. Una tabla
2.2.4.1. Una tabla finita de instrucciones.
2.3. Funcionamiento
2.3.1. Puede considerarse como un autómata capaz de reconocer lenguajes formales. En este sentido es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de chomsky.
2.4. Modificaciones
2.4.1. Máquina de turing con movimiento de espera
2.4.2. Máquina de turing con cinta infinita a ambos lados
2.4.3. Máquina de turing con cinta multipista
2.4.4. Máquina de turing multi cinta
2.4.5. Máquina de turing multidimensional
2.5. Clasificación
2.5.1. Máquina de turing determinista
2.5.1.1. Para cada estado o símbolo posible exista a lo sumo una posibilidad de ejecución, aquí se dirá que es una máquina de turing determinista.
2.5.2. Máquina de turing no determinista
2.5.2.1. En caso contrario al anterior de que exista al menos un par estado o símbolo con más de una posible combinación de actuaciones se dirá que se trata de una máquina de turing no determinista.
3. Autómatas finitos
3.1. ¿Qué es?
3.1.1. Es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
3.2. Se conforman
3.2.1. Un alfabeto
3.2.2. Un conjunto de estados finitos
3.2.3. Una función de transición
3.2.4. Un estado inicial
3.2.5. Un conjunto de estados finales
3.3. Funcionamiento
3.3.1. Se basa en una función de transición, que reciba a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto, y qué va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse un estado final o de aceptación que representa la salida.
3.4. Finalidad
3.4.1. Es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la jerarquía de Chomsky
3.5. Representación
3.5.1. Como diagramas de estados
3.5.2. Como tabla de transiciones
3.6. Clasificación
3.6.1. Autómata finito determinista
3.6.1.1. Es un autómata finito que además es un sistema determinista; es decir, para cada estado q € Q en que se encuentra el autómata, y con cualquier símbolo a € £ del alfabeto leído, existe siempre a lo más una transición posible.
3.6.2. Autómata finito no determinista
3.6.2.1. Es aquel que, a diferencia de los autómatas finitos deterministas posee al menos un estado q € Q tal que para un símbolo a € £ del alfabeto existe más de una transición posible.
4. Autómata linealmente acotado
4.1. ¿Qué es?
4.1.1. Se trata de una máquina de turing limitada en la cantidad de cinta o memoria que posee. Las computadoras de propósito general que existen físicamente son equivalentes a estas máquinas.