PROGRAMA DE INGENIERIA EN SISTEMAS

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

...