57_col1_301405

TRABAJO COLABORATIVO

AUTOMATAS Y LENGUAJES FORMALES

JONATHAN ALEXIS ARANGO LONDOÑO

Cod:1088270195

MAGDA CRISTINA GRIJALBA

Cod:

LIZETH LILIANA ZUÑIGA CAIPE

Cod:1089290172

Curso: 301405_57

PRESENTADO A:

JAIME JOSE VALDES

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA

PROGRAMA INGENIERIA DE SISTEMAS

OCTUBRE DE 2013

ACTIVIDADES A DESARROLLAR

Para el siguiente Autómata Finito denotado como: 𝐴2 = (𝐸 = {1,2,3}, 𝑄 = {𝑞1, 𝑞2, 𝑞3} 𝑓, 𝑞1, 𝐹 =

{𝑞2})donde 𝒇 viene dada por la siguiente tabla:

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

2. Construya el diagrama de Moore correspondiente.

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

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

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

función.

6. Identifique el lenguaje que genera.

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

cada secuencia.

𝒇 1 2 3

𝒒𝟏 𝑞1 𝑞1 𝑞2

𝒒𝟐 𝑞3 𝑞3 𝑞3

𝒒𝟑 𝑞3 𝑞3 𝑞3

8. Muestre el diagrama de Moore generado en JFLAp y en VAS y comente que

similitudes o diferencias encuentra al realizarlo en los dos simuladores. (herramientas

que ofrezca uno u otro).

9. Genere la tabla de transición en VAS y plásmela en el documento, compárela con la

plasmada en el ejercicio.

10. Por último, identifique las cadenas válidas que generan las siguientes ER: muestre

algunas, pero más que las cadenas identifique el lenguaje que representa. Seleccione

una ER (solo una) y expórtela o genere el autómata o el diagrama de Moore que sea

válido.

si A = {0,1}

a) 0*+1*(01)

b) 10* + 10

c) 01* + 0

d) (1.11*0) *

e) (1 + 10) + 0

f) 1* 0*10

g) 00* 11*

h) (0+1)*11(1+0)*

Solución

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

2. Construya el diagrama de Moore correspondiente.

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

El autómata dado es un AFD (Autómata Finito Determinista) ya que en cada estado solo

existe un solo camino para cada elemento del alfabeto.

Ejemplo:

Si observamos el estado 𝑞2 tenemos tres transiciones, una para cada elemento del alfabeto

lo que significa que el autómata solo tiene una opción para cada transición.

𝒇 1 2 3

−> 𝒒𝟏 𝑞1 𝑞1 𝑞2

# 𝒒𝟐 𝑞3 𝑞3 𝑞3

𝒒𝟑 𝑞3 𝑞3 𝑞3

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

𝐴2 = (𝐸 = {1,2,3}, 𝑄 = {𝑞1, 𝑞2, 𝑞3} 𝑓, 𝑞1, 𝐹 = {𝑞2})

Sea el Autómata finito 𝐴2, cuyo alfabeto E está conformado por los símbolos 1,2, y 3,

y tiene un conjunto de estados Q conformado por los estados 𝑞1, 𝑞2, 𝑦 𝑞3, que tiene

un estado inicial 𝑞1 y un estado final F=𝑞2, y con una función de transición 𝒇 que viene

dada por la siguiente tabla:

Para mayor claridad se tienen las siguientes definiciones:

Autómata: La palabra autómata evoca algo que pretende imitar las funciones propias

de los seres vivos, especialmente relacionadas con el movimiento, por ejemplo el

típico robot antropomorfo. Un ejemplo de una “maquina real” que automatiza un

proceso puede ser una máquina empacadora de algún producto que se fabrique en

serie y con una serie de instrucciones, pasos y características definidas e iguales para

cada salida (producto final).

Alfabeto: Un Alfabeto es un conjunto finito A. Sus elementos se llamaran símbolos o

letras. Para denotar el alfabeto se usara el símbolo Σ o en algunos casos se

especificaran con las primeras letras mayúsculas del abecedario, dependiendo como

se formule el problema. Los símbolos de un alfabeto pueden ser números, letras, entre

otros y suelen estar escritos en minúsculas.

Ejemplo: Sea A = {0,1} indica el Alfabeto A compuesto por los símbolos 0,1

Estado: Un estado es un conjunto particular de instrucciones las cuales serán

ejecutadas en respuesta a la entrada de la máquina. Se puede pensar en el estado

como algo análogo a la memoria principal de la computadora. El comportamiento del

sistema es una función de (a) la definición del autómata, (b) la entrada y (c) el estado

actual.

𝒇 1 2 3

−> 𝒒𝟏 𝑞1 𝑞1 𝑞2

# 𝒒𝟐 𝑞3 𝑞3 𝑞3

𝒒𝟑 𝑞3 𝑞3 𝑞3

Función de transición: Una función de transición en teoría de autómatas, es una

función que define las transiciones entre los estados de una Máquina de Turing, de un

autómata finito o de otro tipo de autómatas. Se describe mediante una tabla de

transición de estados.

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

función.

La expresión regular que representa el autómata está dada por: (1 + 2)∗. 3

Explicación:

Operadores:

+ (∪ ó 𝑼𝒏𝒊ó𝒏): La unión de conjuntos A y B se denota por 𝐴 ∪ 𝐵 y es un conjunto

formado por los elementos que aparecen en A, en B o en ambos.

* (Estrella o Clausura de Kleene): La clausura de Kleene es una operación unaria

que se aplica sobre un conjunto de cadenas de caracteres o un conjunto de símbolos

o caracteres (alfabeto), y representa el conjunto de las cadenas que se pueden formar

tomando cualquier número de cadenas del conjunto inicial, posiblemente con

repeticiones, y concatenándolas entre sí.

. (Concatenación): Es la operación por la cual dos caracteres se unen para formar

una cadena de caracteres. También se pueden concatenar dos cadenas de caracteres

o un carácter con una cadena para formar una cadena de mayor tamaño

La expresión regular del autómata tratado nos plantea lo siguiente:

(1+2) 1 unido 2: nos indica que el autómata puede recibir cadenas que comiencen

por 1 o por 2 o por ambos; y si a esto se le agrega la Estrella de Kleene (*) nos

indica que puede comenzar por cualquier cantidad de unos o por ninguno, cualquier

cantidad de dos o por ninguno, o por cualquier cantidad de ambos; y si además se

tiene una concatenación de esta expresión inicial con el número 3 quedando la ER

así (1 + 2)∗. 3 nos indica que el autómata recibe todas las posibles cadenas que

inicien por varios unos o por ninguno, por varios dos o por ninguno, y que finalicen en

tres.

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_aut%C3%B3matas

http://es.wikipedia.org/wiki/Estado_%28inform%C3%A1tica%29

http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing

http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito

http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados

http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados

http://es.wikipedia.org/wiki/Operaci%C3%B3n_unaria

http://es.wikipedia.org/wiki/Conjunto

http://es.wikipedia.org/wiki/Cadena_de_caracteres

http://es.wikipedia.org/wiki/Cadena_de_caracteres

A continuación se listan algunas cadenas aceptadas por el autómata:

6. Identifique el lenguaje que genera.

El lenguaje que el autómata genera está dado por: 𝑳 = {𝝎 𝝐 {𝟏, 𝟐, 𝟑}∗| 𝝎 = (𝟏, 𝟐)∗𝟑}

Explicación:

El lenguaje L es igual a las cadenas que pertenezcan a todas las posibles

combinaciones formadas por los elementos del alfabeto 1,2 y 3, tal que cada cadena

inicie por varios unos o por ninguno, por varios dos o por ninguno, y que finalicen en

tres.

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

cada secuencia.

1. Se inicializa el autómata en el estado q1y se inicia el recorrido con la cadena

11123:

2. Se genera el primer 1 de la cadena en el estado q1

3. Se genera el segundo 1 de la cadena sin cambiar de estado

4. Se genera el tercer y último 1 de la cadena sin cambiar de estado

5. Se genera el único 2 de la cadena sin cambiar de estado

6. Se genera el 3 para cambiar al estado de aceptación q2 y finalizar el proceso

8. Muestre el diagrama de Moore generado en JFLAp y en VAS y comente que similitudes

o diferencias encuentra al realizarlo en los dos simuladores. (Herramientas que ofrezcan

uno u otro).

DIAGRAMA DE MOORE EN JFLAP

DIAGRAMA DE MOORE EN VAS

ANALISIS DE AMBOS SIMULADORES

Ambos simuladores permiten el análisis de cadenas devolviendo aceptación o

rechazo.

En los diagramas de Moore VAS permite la observación de los caminos que toma

cada símbolo en una transición; cosa que no permite JFLAP.

JFLAP permite la inserción de varias cadenas para su posterior análisis.

Ambos simuladores permiten la conversión de AFND a AFD.

Ambos simuladores permiten observar el recorrido paso a paso de un autómata.

JFLAP permite la conversión de AF a ER y viceversa.

VAS permite la visualización de la tabla de transición.

Ambos simuladores permiten la conversión a formato de imagen.

9. Genere la tabla de transición en VAS y plásmela en el documento, compárela con la

plasmada en el ejercicio

Comparando esta tabla de transición con la planteada en el ejercicio se puede observar un

similitud de un 100% entre ellas, en lo que a las transiciones se refiere, sin embargo la tabla

generada por el simulador no muestra el estado inicial ni el de aceptación.

10. Por último, identifique las cadenas válidas que generan las siguientes ER: muestre

algunas, pero más que las cadenas identifique el lenguaje que representa. Seleccione una

ER (solo una) y expórtela o genere el autómata o el diagrama de Moore que sea válido.

si A = {0,1}

a) 0*+1*(01)

Algunas Cadenas aceptadas

0000000000000000

11111111111101

101

01

Lenguaje que representa:

𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟎∗ + 𝟏∗(𝟎𝟏)}


combinaciones formadas por los elementos del alfabeto 0,1 tal que cada cadena

inicie y termine con cero o no lo haga, inicie con varios unos o ninguno, pero con la

condición de que cada vez que inicie por uno debe estrictamente terminar en 01.

b) 10* + 10


10

10000000000000000


𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟏𝟎∗}



este conformada estrictamente por un solo 1, o que inicie estrictamente con un solo 1

y termine o no por un solo o varios 0.

Diagrama de Moore valido para este autómata

c) 01* + 0


10

10000000000000000


𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟎𝟏∗}



este conformada estrictamente por un solo cero, o que inicie estrictamente con un solo

0 y termine o no por un solo o varios 1.

d) (1.11*0) *


𝝀

111111011111101111110

110110110

11111110

10

𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = (𝟏𝒊𝟎)∗|𝒊 ≥ 𝟐}


combinaciones formadas por los elementos del alfabeto 0,1 tal que cada cadena sea

la cadena vacía, o repita o no, una secuencia que comienza estrictamente con dos o

más unos, y termina estrictamente con un solo 0.

EJEMPLO:

110110110 (se repite tres veces la secuencia 110)

1111110111111011111101111110 (se repite cuatro veces la secuencia 1111110)

e) 1* 0*10


1111111111111111111111110000000000000000010

1010

10

000000000000000000000000010

11111111111111111111111111111111111110


𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟏∗𝟎∗𝟏𝟎}



comience por varios, uno o ningún 1, comience por varios, uno o ningún 0, pero que

estrictamente finalice con 10.

f) 00* 11*


01

00000000000000000000000011111111111111111111111111111

0000111111


𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟎𝒏𝟏𝒎| 𝒏 𝒚 𝒎 ≥ 𝟏}



comience por un solo o varios 0, y termine con uno o varios 1.

BIBLIOGRAFIA

- Amaya Tarazona, Carlos Alberto; Modulo del curso Autómatas y Lenguajes

Formales; Universidad Nacional Abierta y a Distancia; Colombia 2013.

- Definición de Estado

http://es.wikipedia.org/wiki/Estado_%28inform%C3%A1tica%29 tomado de

Internet el día 13 de octubre de 2013.

- Definición de Función de Transición

http://es.wikipedia.org/wiki/Funci%C3%B3n_de_transici%C3%B3n Tomado

de Internet el día 13 de Octubre de 2013.

http://es.wikipedia.org/wiki/Estado_%28inform%C3%A1tica%29

http://es.wikipedia.org/wiki/Funci%C3%B3n_de_transici%C3%B3n

Documents

57_col1_301405