TrabCol_Momento1_301405_15
Páginas: 5 (1186 palabras)
Publicado: 23 de octubre de 2015
AUTÓMATAS Y LENGUAJES FORMALES
Actividad Momento 1
JAIME JOSE VALDES
TUTOR
301405_15
ANDRES LEONARDO BELTRAN LÓPEZ
C.C. 80849670
UNIVERSIDAD ABIERTA Y A DISTANCIA – UNAD
CEAD – JOSE ACEVEDO Y GÓMEZ
BOGOTÁ D.C. - 2015
INTRODUCCIÓN
Las expresiones regulares tienen como objetivo principal el representar todos los lenguajes definidos posibles basándose en un alfabeto y con base a unaserie de primitivos lenguajes junto con los operadores que lo componen
¿Qué es un lenguaje primitivo?
Se refiere a un tipo de lenguaje vacío, formado por una palabra vacía y todo aquel símbolo distinto al alfabeto
Ø
Λ
a, siendo a ∈ Σ
¿Cuáles son los operadores de composición?
La unión
La concatenación
El cierre
Ejemplos:
Un lenguaje formado por las cadenas que terminan en 01 puede ser:
a)= (
Expresión regular: (0+1)*01
DESARROLLO DE LA ACTIVIDAD
1.
Las expresiones regulares (ER), pueden también escribirse de otras formas o con otra secuencia de operadores o distribución de símbolos. En general es una forma matemática que representa el Lenguaje que genera un Autómata. Y esas expresiones regulares siempre serán válidas siempre y cuando representen exactamente elmismo lenguaje para un Autómata. Concluyendo, para un Autómata, puede haber más de una ER que representa el mismo lenguaje ya sea que esa ER sea minimizada, extensa, equivalente o como se prefiera escribir. Solo que en los diseños óptimos computacionales siempre se buscará la mejor ER (corta o mínima) para efectos de la mejor simulación o para llevarlas a lenguajes de programación en la creación desoluciones computacionales (solucionar problemas - Algoritmos)
Dada las siguientes expresiones regulares (ER), encuentre la expresión mínima simplificada correspondiente y una posible expresión equivalente escrita de otra forma. (para ello, siempre tenga en cuenta la jerarquía de caracteres y el tema de ER descrito en el módulo).
ER
ER SIMPLIFICADA
ER1
(0(1)*)+1
01111
ER2ʎ+1+(ʎ+1)(ʎ+1)*(ʎ+1)
ʎ111
ER3
0+(ʎ+1)(ʎ+1)*0
0110
ER4
1*0+1*0(ʎ+0+1)*(ʎ+0+1)
1110+011
ER5
((0+1)1)
1
2. Para la expresión regular 4: 1*0+1*0(ʎ+0+1)*(ʎ+0+1) resuelva:
ʎ
0
1
Q0
{ Q0, Q3 }
{ Q0, Q3 }
Q1
Ø
Q2
Q2
Q2
Q2
Q3
Q4
Ø
Q4
Q4
Q4
1. Describa la forma matemática del autómata
2. Plasme la tabla de transición, identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta.Es un Autómata Finito Determinísticos AFD: debido a que están determinando la ruta por donde puedo pasar o recrear o correr las cadenas que puede aceptar el autómata.
3. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definicionesadicionales.
Ʃ= (0,1) es el alfabeto que contiene estos dos símbolos
K = son los estados que contiene el autómata
S =
F =
= Ʃ X K = K, la función de transición indica a qué estado va a pasar, teniendo conocimiento del estado actual y el símbolo que está leyendo Donde la función x (0,1) =
Está dada por:
=
= Ø =
= =
= = Ø
= =
4. Identifique el lenguaje que genera.
Deacuerdo a la tabla de transiciones y el diagrama anterior, es una cadena que debe tener 2 estados iguales en cualquier parte de la cadena “00” ó “11” y debe iniciar en la cadena con un 0 o con un 1. El lenguaje aceptado por el autómata es:
L = (0,1)
- 00
- 11
5. Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura lasimágenes, estas deben ser explicadas en pie de página o de lo contrario no tienen validez)
La cadena 1001 es una palabra aceptada
Se inicializa la entrada del autómata en
La palabra 1001 inicia con uno (1) y hay dos opciones que se puede optar por tomar, uno de ellos se queda en el mismo estado y se puede realizar un cambio a
La palabra 1001 continúa con un cero (0), la...
AUTÓMATAS Y LENGUAJES FORMALES
Actividad Momento 1
JAIME JOSE VALDES
TUTOR
301405_15
ANDRES LEONARDO BELTRAN LÓPEZ
C.C. 80849670
UNIVERSIDAD ABIERTA Y A DISTANCIA – UNAD
CEAD – JOSE ACEVEDO Y GÓMEZ
BOGOTÁ D.C. - 2015
INTRODUCCIÓN
Las expresiones regulares tienen como objetivo principal el representar todos los lenguajes definidos posibles basándose en un alfabeto y con base a unaserie de primitivos lenguajes junto con los operadores que lo componen
¿Qué es un lenguaje primitivo?
Se refiere a un tipo de lenguaje vacío, formado por una palabra vacía y todo aquel símbolo distinto al alfabeto
Ø
Λ
a, siendo a ∈ Σ
¿Cuáles son los operadores de composición?
La unión
La concatenación
El cierre
Ejemplos:
Un lenguaje formado por las cadenas que terminan en 01 puede ser:
a)= (
Expresión regular: (0+1)*01
DESARROLLO DE LA ACTIVIDAD
1.
Las expresiones regulares (ER), pueden también escribirse de otras formas o con otra secuencia de operadores o distribución de símbolos. En general es una forma matemática que representa el Lenguaje que genera un Autómata. Y esas expresiones regulares siempre serán válidas siempre y cuando representen exactamente elmismo lenguaje para un Autómata. Concluyendo, para un Autómata, puede haber más de una ER que representa el mismo lenguaje ya sea que esa ER sea minimizada, extensa, equivalente o como se prefiera escribir. Solo que en los diseños óptimos computacionales siempre se buscará la mejor ER (corta o mínima) para efectos de la mejor simulación o para llevarlas a lenguajes de programación en la creación desoluciones computacionales (solucionar problemas - Algoritmos)
Dada las siguientes expresiones regulares (ER), encuentre la expresión mínima simplificada correspondiente y una posible expresión equivalente escrita de otra forma. (para ello, siempre tenga en cuenta la jerarquía de caracteres y el tema de ER descrito en el módulo).
ER
ER SIMPLIFICADA
ER1
(0(1)*)+1
01111
ER2ʎ+1+(ʎ+1)(ʎ+1)*(ʎ+1)
ʎ111
ER3
0+(ʎ+1)(ʎ+1)*0
0110
ER4
1*0+1*0(ʎ+0+1)*(ʎ+0+1)
1110+011
ER5
((0+1)1)
1
2. Para la expresión regular 4: 1*0+1*0(ʎ+0+1)*(ʎ+0+1) resuelva:
ʎ
0
1
Q0
{ Q0, Q3 }
{ Q0, Q3 }
Q1
Ø
Q2
Q2
Q2
Q2
Q3
Q4
Ø
Q4
Q4
Q4
1. Describa la forma matemática del autómata
2. Plasme la tabla de transición, identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta.Es un Autómata Finito Determinísticos AFD: debido a que están determinando la ruta por donde puedo pasar o recrear o correr las cadenas que puede aceptar el autómata.
3. Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definicionesadicionales.
Ʃ= (0,1) es el alfabeto que contiene estos dos símbolos
K = son los estados que contiene el autómata
S =
F =
= Ʃ X K = K, la función de transición indica a qué estado va a pasar, teniendo conocimiento del estado actual y el símbolo que está leyendo Donde la función x (0,1) =
Está dada por:
=
= Ø =
= =
= = Ø
= =
4. Identifique el lenguaje que genera.
Deacuerdo a la tabla de transiciones y el diagrama anterior, es una cadena que debe tener 2 estados iguales en cualquier parte de la cadena “00” ó “11” y debe iniciar en la cadena con un 0 o con un 1. El lenguaje aceptado por el autómata es:
L = (0,1)
- 00
- 11
5. Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura lasimágenes, estas deben ser explicadas en pie de página o de lo contrario no tienen validez)
La cadena 1001 es una palabra aceptada
Se inicializa la entrada del autómata en
La palabra 1001 inicia con uno (1) y hay dos opciones que se puede optar por tomar, uno de ellos se queda en el mismo estado y se puede realizar un cambio a
La palabra 1001 continúa con un cero (0), la...
Leer documento completo
Regístrate para leer el documento completo.