Automatas Y Lenguajes Formales Colaborativo 3

TRABAJO COLABORATIVO 3

AUTOMATAS Y LENGUAJES FORMALES

RICHARD GRANADOS GOMEZ

UNIVERSIDAD ABIERTA Y A DISTANCIA UNAD

NOVIEMBRE 2013

TRABAJO COLABORATIVO 3

AUTOMATAS Y LENGUAJES FORMALES

RICHARD GRANADOS GOMEZ

CODIGO: 7.601.164

GRUPO: 301405_5

TUTOR: CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD ABIERTA Y A DISTANCIA UNAD

ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

NOVIEMBRE 2013

INTRODUCCION

La máquina de Turing tiene, como los autómatas que hemos visto antes, un control finito, una cabeza lectora y una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende indefinidamente, llenándose los espacios con el carácter blanco. La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el extremo izquierdo. En la MT la cabeza lectora es de lectura y escritura, por lo que la cinta puede ser modificada en curso de ejecución. Además, en la MT la cabeza se mueve bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobre un mismo segmento de la cinta.

En el presente trabajo se demostrara la utilización de la quina de Turing para resolver autómatas capaces de implementar un modelo matemático q se puede expresar mediante un algoritmo dado, de este modo se resolverá mediante pasos e implementaciones que lean y ejecuten un determinado lenguaje

OBJETIVOS

GENERAL

Verificar el uso, la lectura y escritura de la máquina de Turing demostrando la importancia para la resolución de problemas de cómputo mediante la lectura de lenguajes específicos.

ESPECIFICOS

 Determinar los pasos para realizar un reconocimiento de lenguaje.

 Graficar los diferentes estados de la máquina y su comportamiento con diferentes lenguajes.

 Conocer la importancia de la máquina de Turing como modelo de algoritmo de decisión.

 Diseñar máquinas de Turing para reconocer lenguajes de diversa complejidad y comprender que no todos los lenguajes son reconocibles por una máquina de Turing.

EJERCICIO 1: Diseñe una MT que reconozca el lenguaje de cadenas Máquina que acepta el lenguaje de palabras sobre {0,1} que comienzan y acaban con el mismo símbolo

Se muestra entonces la cadena del lenguaje descrito, aceptada: 0110100 (Estado de aceptación q5).

Las transiciones, y el proceso seguido en la evaluación y aceptación de una cadena dada, se resumen en la siguiente tabla:

Cadena del lenguaje descrito, rechazada: 110

1. Identifique los componentes de la Máquina de Turing (descríbala).

Una máquina de Turing se define como un quíntuplo

MT= (Q, ∑, ┌, ∂, q0, qF) donde:

Q= conjunto de estados tal que h Є Q

∑=Es el alfabeto de entrada (palabras de entrada) donde µ Ɇ ∑

┌= es el alfabeto de la cinta donde µЄ┌ y ∑ Є Ċ ┌

q0= estado inicial

qF= estado aceptador ∑

2. Diséñela en un Diagrama de Moore

3. Recorra la máquina con al menos una cadena válida.

4. Identifique una cadena que no sea válida y justifíquela porque.

Cadena

RRRR

No es válida porque el autómata reconoce solo en lenguaje {x,y, Ø } Ø Ø ¬

No es válido porque no sigue la secuencia de la cinta del autómata

5. Ejecute el RunTest a la cadena aceptada (muéstrela en la captura de imagen para

...