Lenguajes y Autómatas 1

martes, 1 de octubre de 2019

Abreviar palabras - Programa

Abreviar oraciones - 1° letra

Maquina de Turing - Investigacion

¿Qué es una máquina de Turing y cómo funciona?

La llamada “Máquina de Turing” es en realidad un modelo matemático consistente en un autómata que es capaz de “implementar cualquier problema matemático expresado a través de un algoritmo”. A pesar de esta definición tan complicada, en realidad la máquina de Turing destaca por su simplicidad pues manipula símbolos sobre una tira de cinta siguiendo una serie de reglas. A pesar de esta simplicidad, una máquina de Turing puede adaptarse para que simule la lógica de cualquier algoritmo de computador, de ahí su enorme potencial y valor.

Uno de los teoremas más importantes sobre las máquinas de Turing es que pueden simular el comportamiento de una computadora (almacenamiento y unidad de control).
Por ello, si un problema no puede ser resuelto por una de estas máquinas, entonces tampoco puede ser resuelto por una computadora

Teoremas sobre las máquinas de Turing

Recordemos que llamamos lenguaje Recursivamente Enumerable (RE) a los lenguajes que pueden ser aceptados por una Máquina de Turing.

Teorema 1 Todo lenguaje aceptado por una Máquina de Turing de varias cintas es Recursivamente Enumerable.

Teorema 2 Sea L = L(M) el lenguaje que acepta una máquina de Turing no determinista M, entonces existe una máquina de Turing deterministaN que acepta dicho lenguaje, es decir, L(M) =L (N).

Esta máquina de Turing está definida sobre el alfabeto

$\Sigma =\{a,b,c\}$ , posee el conjunto de estados

$Q=\{q_{o},q_{1},q_{2},q_{3},q_{4},q_{5},q_{6}\}$ , con las transiciones que se pueden ver. Su estado inicial es $q_{0}$ y el estado final es $q_{2}$ , el lenguaje de salida
$\Gamma =\{X,Y,Z,B\}$ siendo $B$ el símbolo denominado "blanco". Esta máquina reconoce la expresión regular de la forma $a^{n}b^{n}c^{n}$ con

$n>=0$ .

Apuntes 01 - Octubre - 2019

miércoles, 18 de septiembre de 2019

Automatas de Pila - Ejemplo

Automatas de Pila - Investigacion

Los autómatas de pila, en forma similar a como 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.

Un autómata de pila cuenta con una cinta de entrada y un mecanismo de control que puede encontrarse en uno de entre un número finito de estados. Uno de estos estados se designa como estado inicial, y además algunos estados se llaman de aceptación o finales. A diferencia de los autómatas finitos, los autómatas de pila cuentan con una memoria auxiliar llamada pila. Los símbolos (llamados símbolos de pila) pueden ser insertados o extraídos de la pila, de acuerdo con el manejo last-in-first-out (LIFO).

Las transiciones entre los estados que ejecutan los autómatas de pila dependen de los símbolos de entrada y de los símbolos de la pila. El autómata acepta una cadena x si la secuencia de transiciones, comenzando en estado inicial y con pila vacía, conduce a un estado final, después de leer toda la cadena x.

La función de transición de estados de un AP puede ser representada por un diagrama donde los nodos representan los estados y los arcos transiciones. Si existe transición tipo (1), el arco queda rotulado de la siguiente manera:

Si el estado actual es ei y la cabeza lectora apunta un símbolo a, y el tope de la pila es X, entonces cambiar al nuevo estado ej, avanzar la cabeza lectora, y sustituir el símbolo del tope X en la pila por la cadena α.

Si α = ZYX deja X , apila Y, y apila Z (nuevo tope Z). donde X, Y, Z ∈ P

Si α =XX                deja X y apila X (nuevo tope X).
Si α =X                  deja X como el mismo tope (no altera la pila)
Si α =ε                   elimina X, y el nuevo tope es el símbolo por debajo (desapila)