TRABAJO COLABORATIVO No 1 AUTOMATAS

INTRODUCCION

Reconocer y aplicar los lenguajes regulares, autómatas finitos y su aplicación en ejercicios donde se evalué su desempeño y desarrollo, mediante un trabajo colaborativo.

DESARROLLO DEL TRABAJO

Para el siguiente Autómata Finito denotado como:

Donde f viene dada por la siguiente tabla

f 1 2 3

q1 q1 q1 q2

q2 q3 q3 q3

q3 q3 q3 q3

1. Corrija la tabla de transición indicando el estado inicial y el final

f

1 2 3

q1

q1 q1 q2

#q2 q3 q3 q3

q3 q3 q3 q3

Función de transición 

Construya el diagrama de moore correspondiente

2. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta

El Autómata es un AFD

Justificación:

Porque posee la característica del determinismo la cual permite saber a partir del estado actual y del símbolo actual de entrada poder determinar en forma exacta cual será el estado siguiente.

3. Identifique los elementos (tupla que es). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales.

En el anterior autómata vemos que se trata de una quíntupla la cual está compuesta por los siguientes elementos.

Alfabeto de entrada Identificado con la letra E y contiene los símbolos del alfabeto en este caso {1, 2, 3} y su función en el autómata es la de formar una cadena de símbolos o un lenguaje.

Conjunto de estados Identificado con la letra Q y que contiene 3 estados en este caso {q1, q2, q3} y son los que van a guardar la memoria de las configuraciones del autómata.

Función de transición En este caso se encuentra representada por la letra f, y está definida por donde Q son los estados y E el alfabeto de entrada, y nos indica a qué estado se va a pasar sabiendo cual es el estado actual y el símbolo que se está leyendo.

Estas son las funciones de transición a partir de la tabla de transición anteriormente dada.

Estado inicial En este caso representado por , y gráficamente se representa de la siguiente manera

Desde este estado se empiezan a leer los diferentes símbolos o cadenas que se ingresen en el AFD

Estado final En nuestro autómata se representa por la letra F y nos dice que nuestro estado de aceptación o final es , y es en este estado donde nos indica si nuestra cadena de símbolos es aceptada o rechazada. Gráficamente se representa de la siguiente manera

4. Identifique la ER que lo representa. Explique los operadores y cómo actúan en la función.

La expresión regular que lo representa es:

Los operadores de esta ER son:

( )  Operador de agrupación y define perímetros de una ER.

+  Operador de cuantificación y nos indica que el carácter que lo precede puede ir al menos una vez o más veces en la cadena. (Representa la unión)

*  Operador de cuantificación y nos indica que el carácter que lo precede puede ir en la cadena cero veces , una vez o más veces. (estrella de kleene).

De acuerdo con esta ER , entonces ingresamos una cadena y verificamos si es aceptada o rechazada.

5. Identifique el lenguaje que genera.

El autómata genera el lenguaje de todas las cadenas w posible dentro del conjunto de combinaciones {1, 2, 3}, de tal manera que esas cadenas siempre terminen en 3 ; y empiecen por 1 , por 2 o por ninguno.

6. Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia.

En este gráfico ingresamos

...