PROGRAMA DE INGENIERIA EN SISTEMAS
Enviado por javier marmolejo serrano • 12 de Abril de 2016 • Trabajos • 1.737 Palabras (7 Páginas) • 345 Visitas
[pic 1]
FASE INICIAL MOMENTO 1
Javier Marmolejo Serrano
Código 16.276.985
Tutor curso
Víctor Fernando Canon Rodriguez
Autómatas y Lenguajes Formales
301405_20
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA
UNAD
FACULTAD DE CIENCIAS BASICAS E INGENIERIA
PROGRAMA DE INGENIERIA EN SISTEMAS
PALMIRA MARZO 20 DE 2.016
INTRODUCCION
En este trabajo individual se procederá a desarrollar dos problemas de Autómatas en el Visual autómata simulador para practicar y entender como funcionan.
OBJETIVO GENERAL
Practicar en el simulador Visual Autómata realizando dos ejercicios para adquirir conocimientos.
PRODUCTOS SOLICITADOS
Desarrollar
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 el mismo 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 de soluciones computacionales (solucionar problemas - Algoritmos) Dados los siguientes ítems, Autómatas Finitos Deterministas, Autómatas Finitos no Deterministas, lenguajes y expresiones regulares (ER), encuentre según corresponda:
[pic 2]
Desarrollo EJ1
AFN / AFD
[pic 3]
Lenguaje
L= {w | w tiene al menos una a y a y tiene al menos una b} sobre {a, b}
Expresión regular
(a U b)*(ab)(a U b)*
Desarrollo EJ2
AFN / AFD
[pic 4]
Lenguaje
L = {w │w empieza por b y termina con a} sobre {a,b}
Expresión regular
bb*aa*
Desarrollo EJ3
AFN / AFD
[pic 5]
Lenguaje
El lenguaje de las palabras que tiene abb o bba por subcadena
Expresión regular
(a U b)*(abb U bba)(a U b)*
Desarrollo EJ4
AFN / AFD
[pic 6]
Lenguaje
Cadenas que comienzan con a y le siguen o no f's y terminan en b o las cadenas que empiezan con la letra d y le siguen o no g's y terminan en j o las cadenas vacias.
Expresión regular
(af*b U dg*c)*
Desarrollo EJ5
AFN / AFD
[pic 7]
Lenguaje
(ab U c)*d
Expresión regular
L = {w │w contiene la subcadena ab o la letra c o ninguna de estas dos y w termina en d} sobre {a,b,c,d}
[pic 8]
(cb)*ca(ab)*U b(ba)*b U (ab)*a(ba)*b aquí esta expresado en u=+ Union (Precedencia de los operadores).
(ab)*b=(ba) aquí usamos esta ley r(sr)* = (rs)*r Pasos a segurar:
1. Primera simplificación de la expresión regular (ER) (cb)*ca(ab)*+ b(ba)*b + (ba)*a(ba)*b
2. Sacamos factor común ba(ba)* y queda (cb)*ca(ab)*U b(ba)*ba(ba)*
3. Usamos esta forma (aa)*a = a(aa)* , r(sr)* = (rs)*r y queda: (cb)*c= c(cb) , a(ab)*=(ab)*
4. sacamos factor común a la expresión ba(ba)* y la aplicamos a: c(Cb)* a(ba)*+ba(ba)*
Y queda: c(Cb)* ab(ba)* ((cb)*ca+(bb+ab))(ab)* asi queda, dice el tutor.
Autómata grafico
[pic 9]
1. Describa la forma matemática del autómata.
[pic 10]
2. Plasme la tabla de transición.
Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo sino de justificarlo asociando la respuesta al diseño del autómata).
Transición
ṑ (q0, c)=q1
ṑ (q1, c)=q1
ṑ (q1, b)=q1
ṑ (q1, a)=q2
ṑ (q2,a)=q2
ṑ (q2, b)=q2
ṑ (q2, b)= q2
Tablas de transición:
A b c
q0 / / q1
q1 q2 q1 q1
q2 q2 (q1, q2) /
Este autómata no es un AFD porque la combinación no produce un solo estado, es un AFND porque el estado Q0 con símbolo c puede ir al estado q1, y el estado q1 con símbolo a puede ir q2, q1 con símbolo b puede ir a q2.
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 definiciones adicionales.
Una tupla es una secuencia ordenada de objetos, es una lista de elementos con un número limitado de objetos y se emplean para describir objetos matemáticos los cuales pueden ser descompuestos en un número de componentes.
K= {q0, q1, q2} conjunto de estados donde el autómata viaja de un estado a otro.
E= {a, b, c} esta la podemos describir como el alfabeto que utiliza el autómata.
S= {q0} el estado inicial donde inicia el autómata su recorrido por los diferentes estados.
F= {q1} este elemento de la tupla es donde termina el estado final del autómata.
...