Automatas Y Lenguajes Formales

TRABAJO COLABORATIVO 2

AUTOMATAS Y LENGUAJES FORMALES

EULSES OSORIO PEREZ COD. 7701376

ALEXANDER VALDERRAMA COD.

GRUPO

301405_6

TUTOR

CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD ESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA INGENIERIA DE SISTEMAS

2012

INTRODUCCIÓN

Mediante el desarrollo del trabajo colaborativo de la unidad 2 del curso de Autómatas y Lenguajes Formales pretendemos poner en práctica los conceptos básicos aprendidos hasta el momento acerca de los lenguajes independientes del contexto, sus conceptos generales, sus propiedades y su relación con los autómatas a pila.

También es importante complementar la solución de los ejercicios de la actividad a través del uso de herramientas computacionales de simulación, empleando los conceptos aprendidos en nuestros estudios de las diversas ramas de la Ingeniería en nuestra Universidad.

Para ello, se pretende resolver lo solicitado en la guía de la actividad mediante el trabajo individual y colaborativo de los miembros del grupo No. 6 a través de la Plataforma Virtual del curso buscando fomentar la investigación, el trabajo en equipo, el dialogo y la concentración como pilares fundamentales de la filosofía Unadista.

OBJETIVOS

• Conocer los modelos de computación que corresponden a los lenguajes independientes del contexto y su aplicación.

• Generalizar los conceptos de autómatas finitos y gramáticos regulares.

• Reconocer el potencial de procesamiento del lenguaje del autómata con los

Autómatas de pila.

• Desarrollar las competencias comunicativas con sus compañeros de grupo al realizar un trabajo colaborativo concertado bajado en la investigación individual y un dialogo grupal respetuoso y constructivo.

• Afianzar las competencias argumentativas al exponer la resolución de un problema utilizando los conceptos del modulo.

1. Calcular el autómata mínimo correspondiente al siguiente autómata finito determinista.

1. Identifique los componentes del autómata (que tipo de tupla es)

Es un autómata finito deterministico porque desde cualquiera de sus estados sale una sola letra o un solo símbolo para otro estado y se determina con exactitud cual es su llegada.

El autómata está definido por la siguiente quíntupla

:A = (Q, Σ, f, q, F) donde:

• Q es un conjunto de estados.

• Σ es el alfabeto de entrada

• δ: Q X Σ → Q es la función (total) de transición.

• q0 ∈ Q es el estado inicial.

• F⊆ Q es el conjunto de estados finales.

A = ({q0, q1, q2, q3, q4, q5, q6, q7} , {0,1} , δ , qo, { qo,q2, q3, q4, })

f está definida de la siguiente manera:

δ(q0, 0) = q1 δ(q0, 1) = q6 δ(q1, 0) = q2 δ(q1, 1) = q3 δ(q2, 0) = q1

δ(q2, 1) = q5 δ(q3, 0) = q1 δ(q3, 1) = q4 δ(q4, 0) = q7 δ(q4, 1) = q4 δ(q5, 0) = q7 δ(q5, 1) = q3 δ(q6, 0) = q7 δ(q6, 1) = q3 δ(q7, 0) = q7 δ(q7, 1) = q3

2. Identifique la tabla de transición

→

#

#

#

#

3. Identifique el lenguaje que reconoce y las posibles cadenas

4. Encuentre la expresión regular válida. (compruebe una cadena válida de esa expresión regular en el simulador). Identifique sus componentes

9. Explicar el proceso de Minimización (que estados se suprimen y porque).

Para minimizar el autómata se utilizo el algoritmo de minimización que consiste en los siguientes pasos

Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son estados distinguibles. Un estado final con un estado no-final nunca serán equivalentes.

Un AFD está minimizado, si todos sus estados son distinguibles y alcanzables. Un algoritmo de minimización de AFD es el siguiente:

• Eliminar los estados inaccesibles del autómata.

• Construir una tabla con todos los pares (p, q) de estados restantes.

• Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.

• Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s =

δ(q,a):

• Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto marcar la entrada (p, q). De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).

• Agrupar los pares de estados no marcados.

10.Que transiciones se reemplazan o resultan equivalentes.

...