Trabajo Colaborativo 3 Automatas Y Lenguajes Formales

AUTOMATAS Y LENGUAJES FORMALES

TRABAJO COLABORATIVO 3

ANA JOAQUINA ROJAS PARRA

ana.rojasparra@gmail.com

Código: 36.297.351

Cead: Pitalito

ANA MARIA GUAPACHA RUIZ

anyma82@hotmail.com

Código: 38.290.126

Cead: La Dorada

Grupo: 16

CARLOS ALBERTO AMAYA TARAZONA

Tutor

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA

INGENIERIA DE SISTEMAS

AUTÓMATAS Y LENGUAJES FORMALES

NOVIEMBRE 20 DE 2013

INTRODUCCIÓN

Las máquinas de Turing son modelos matemáticos capaces de ejecutar un problema por medio de un algoritmo, este autómata reconoce los lenguajes estructurados por frases que se describen mediante reglas de sobre escritura, donde para los alfabetos existe este tipo de lenguaje su estructura es realizada por frases mediante cadenas que son analizadas por medio de una jerarquía.

En el presente trabajo realizaremos un desarrollo aplicado de los temas vistos en la unidad No.3 del módulo de autómatas y lenguajes formales, vemos funcionamiento, características, codificación de la máquina de Turing y la importancia de los lenguajes estructurados por frases.

Máquina de Turing

Es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. 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 un CPU dentro de un computador.

Es un modelo computacional creado por Alan Turing con el cual él afirmaba que se podía realizar cualquier cómputo.

La máquina de Turing, como modelo matemático, consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.

OBJETIVO GENERAL

Conocer el funcionamiento y la aplicación de las máquinas de Turing aplicada al lenguaje estructurado por frases.

Reconocer la importancia y el poder computacional de las Máquinas de Turing en el contexto de la solución de problemas computacionales de reconocimiento de Lenguajes.

OBJETIVOS ESPECÍFICOS:

 Conocer las principales características de las máquinas de Turing.

 Identificar las propiedades y los lenguajes de las máquinas de Turing.

 Estudiar las Máquinas de Turing y sus propiedades básicas

 Afianzar los conocimientos en la temática a tratar.

 Aprender a manejar el comportamiento de un ejercicio sobre una máquina de Turing, su recorrido, etc.

EJERCICIOS A DESARROLLAR:

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.

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

Dónde:

• es un conjunto finito de estados.

• es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.

• es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta ( ).

• es el estado inicial.

• es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.

• es el conjunto de estados finales de aceptación.

• es una función parcial denominada función de transición, donde es un movimiento a la izquierda y es el movimiento a la derecha.

Existen en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo como símbolo de "no movimiento" en un paso de cómputo.

 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.

MT= (K = {q0, q1, q2, q3, q4, q5}, Ʃ= {0,1}, S= {q0}, T= {q5}, )

K = {q0, q1, q2, q3, q4, q5}= es el conjunto de estados de la MT

Ʃ= {0,1} corresponde al alfabeto de entrada

= es el alfabeto de la cinta

S= {q0} corresponde al estado inicial de la MT

T= {q5} es el estado final

= corresponde a las funciones de transición

2. Diséñela en un Diagrama de Moore

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

...