Upload
jonathan-arango
View
621
Download
0
Embed Size (px)
Citation preview
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.
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:
𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟎∗ + 𝟏∗(𝟎𝟏)}
El lenguaje L es igual a las cadenas que pertenezcan a todas las posibles
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
Algunas Cadenas aceptadas
10
10000000000000000
Lenguaje que representa:
𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟏𝟎∗}
El lenguaje L es igual a las cadenas que pertenezcan a todas las posibles
combinaciones formadas por los elementos del alfabeto 0,1 tal que cada cadena
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
Algunas Cadenas aceptadas
10
10000000000000000
Lenguaje que representa:
𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟎𝟏∗}
El lenguaje L es igual a las cadenas que pertenezcan a todas las posibles
combinaciones formadas por los elementos del alfabeto 0,1 tal que cada cadena
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) *
Algunas Cadenas aceptadas
𝝀
111111011111101111110
110110110
11111110
10
𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = (𝟏𝒊𝟎)∗|𝒊 ≥ 𝟐}
El lenguaje L es igual a las cadenas que pertenezcan a todas las posibles
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
Algunas Cadenas aceptadas
1111111111111111111111110000000000000000010
1010
10
000000000000000000000000010
11111111111111111111111111111111111110
Lenguaje que representa:
𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟏∗𝟎∗𝟏𝟎}
El lenguaje L es igual a las cadenas que pertenezcan a todas las posibles
combinaciones formadas por los elementos del alfabeto 0,1 tal que cada cadena
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*
Algunas Cadenas aceptadas
01
00000000000000000000000011111111111111111111111111111
0000111111
Lenguaje que representa:
𝑳 = {𝝎 𝝐 {𝟎, 𝟏}∗| 𝝎 = 𝟎𝒏𝟏𝒎| 𝒏 𝒚 𝒎 ≥ 𝟏}
El lenguaje L es igual a las cadenas que pertenezcan a todas las posibles
combinaciones formadas por los elementos del alfabeto 0,1 tal que cada cadena
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.