MOMENTO 1 AUTOMATAS

AUTOMATAS Y LENGUAJES FORMALES

MOMENTO 1

CARLOS ANDRES PEREZ SALDAÑA

CARLOS TOVAR

FELIPE AREVALO

TUTOR: JAIME RUBIANO

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

ESCUELA DE INGENIERIAS

INGENIERIA ELECTRONICA

BOGOTA

2015

PROBLEMAS A DESARROLLAR:

Dada las siguientes expresiones regulares (ER) encuentre la expresión mínima simplificada correspondiente:

ER1=(0(1)^* )+1

=(01^* )+1

= 01^*

ER2= λ+1+( λ+1)( λ+1 )^* ( λ+1 )

=(λ+1)+( λ+1)( λ+1 )^* ( λ+1 )

=(λ+1)(λ+ ( λ+1 )^* ( λ+1 ))

=(λ+1)(λ+ ( λ+1)( λ+1 )^* )

=(λ+1)( λ+1 )^*

=(λ+1)1^*

ER3=0+ ( λ+1)( λ+1 )^* 0

=(λ+( λ+1)( λ+1 )^* )0

=(λ+1)^* 0

=1^* 0

ER4=1^* 0+ 1^* 0 ( λ+0+1)^* ( λ+0+1)

= 1^* 0 ( λ+ ( λ+0+1)^* ( λ+0+1))

= 1^* 0 ( λ+0+1)^*

= 1^* 0 ( λ+(0+1))^*

= 1^* 0 ( λ^* (0+1))^* λ^*

〖= 1〗^* 0 ( λ(0+1))^* λ

〖= 1〗^* 0 (0+1)^*

ER5=((0+1)1)

=01+11

Para la expresión regular 4: 1^* 0+ 1^* 0 ( λ+0+1)^* ( λ+0+1), resuelva:

Describa la forma matemática del autómata:

Tomamos la simplificación de la expresión que es:

〖= 1〗^* 0 (0+1)^*

Primero definimos el alfabeto: Σ = {1,0}, y luego procedemos a escribir en notación de conjuntos la función de transferencia:

δ= ( {1}* {0} ) ( {0} U {1} )* = { (1)m (0)} { (0) U (1)}n donde my y son mayores o iguales a cero

Plasme la tabla de transición. Identifique que tipo de autómata es AFD o AFND, y justifique

Podemos empezar dibujando un diagrama de estados:

〖= 1〗^* 0 (0+1)^*

Y Ahora simplificamos:

Con este gráfico es mas facil realizar la tabla de transición:

Este autómata es determinista (AFD) porque:

Por cada nodo solo hay un arco etiquetado con cada uno de los simbolos o 1 o 0

Tiene un estado incial claro y definido Q0

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.

Entonces:

E4 = ( E = {0,1} estos son los elementos del alfabeto que pueden ser caracteres, letras o caracteres especiales, Q = { Q0,Q1} estos son los estados o memorias que determinan un comportamiento dada ciertas interacciones que pueden cambiar dependiendo de cada autómata, despues viene la ft (función de transferencia) que puede ser la tabla de transición ó δ = 1*0 (0+1)*esta FT indica el comportanmiento como tal del autómata asociando estados, simbolos e interacciones; el cuarto elemento es el estado incial Q0 que es donde empieza el autómata y el quinto elemento es el estado final Q1 que es donde finaliza el autómata.

Identifique el lenguaje que genera

Primero definimos lenguaje L como el conjunto de palabras w que son cadenas formadas por simbolo de un alfabeto E

Por lo tanto:

L = { w E {1,0}* / w = 1*0 (0+1)*}

Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura las imágenes, estas deben ser explicadas en pié de página o de lo contrario no tienen validez)

Vamos a utilizar el JFLAB ya que el simualtor no se pudo descargar porque ningun link fue encontrado para descargarlo:

Vamos a ingresar la cadena 001:

El autómata en el simulador es:

Ingresamos la secuencia 001:

Le damos aceptar y miramos que cambia de color Q0:

Al darle step al simulador, el Q0 cambia de color a su color natural y Q1 queda del color verde, esto significa que q0 paso el 0 al q1, el primer 0 de la cadena:

Al volver a darle step pasa el segundo 0, y no cambia de color ya que q1 es el que esta recibiendo el 0:

El último paso sería pasar el 1:

Completando asi la cadena 001

. Muestre el diagrama de Moore generado en JFLAP y en VAS y comente tres similitudes y tres diferencias que encuentra al realizarlo en los dos simuladores. (herramientas que ofrezca uno u otro).

Diagrama de MOORE generado pro JFLAP:

Lastimosamente no pude descargar VAS, ningun link servia….

Genere tres cadenas válidas y dos no válidas.

Es claor que las cadenas aceptadas 000, 1110, 100000001, son válidas ya que pueden pasar cualquier cantidad de unos desde el vacio hasta n…unos, pero siempre acompañados de al menos un CERO, por eso las cadenas 111, 1 no son válidas ya que no tiene al menos algun CERO y es una obligación ya que es el estado que se transporta de Q0 a Q1

Si el autómata inicial (el de la ER4) es un AFD, genere un AFND que reconozca el mismo lenguaje; o por lo contrario si el autómata inicial es un AFND, genere un AFD que reconozca el mismo lenguaje.

un autómata finito determinístico AFD M = (∑, K, δ, q0, F). se puede construir uno no-determinista: M-- = (∑, K, δ--, , q0, F). que acepta el mismo lenguaje. Solo se debe considerar:

δ-- = (q0,a) = { δ (q0,q)}: en el que en cada situación solo hay un camino posible que es el que determine la función de transición δ

Como el primer autómata es un AFD debemos encontrar un AFND, esto lo logramos haciendo redundantes enlaces con los CEROS, asi logramos que un CERO pse envíe por 2 caminos al mismo tiempo desde el mismo q2 ( no determinista):

Describa la forma matemática del autómata:

Lo primero es hallar la ER, esto lo hacemos con el simulador:

El cual nos da:

1*(0+0(0+1)*0)(1+0)*

Entonces tenemos el mismo alfabeto E = {1,0}

y luego procedemos a escribir en notación de conjuntos la función de transferencia:

δ= ( {1}* ({0} U {0}(0 U 1)* {0}) (1 U 0)* = ( {1}m ( 0 U 0 (0 U 1)n {0}) (1 U 0)p donde m, n y p son mayores o iguales a cero

Identifique los elementos (tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto).

E = {1,0} alfabeto

K = q0, q1, q2 estados

δ= 1*(0+0(0+1)*0)(1+0)* función de transferencia

s= q0 estado inicial

f= q1 estado final

Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cadasecuencia. (No se trata solo de captura las imágenes, estas deben ser explicadas en pié de página o de lo contrario no tienen validez)

Vamos a ingresar la secuencia 110:

Como vemos se activa el primer estado q0 con el 1, el cual vuelve al mismo estado q0.

En el segundo paso ya hemos enviado dos unos y como el primer estado nos dice que al ingresar un 1 se devuelve al mismo estado, entonces no se activa ninguna otra:

ahora avanzamos para el ingreso del cero:

En este se activa tanto q2 como q1, ya que el cero es paso obligado dede q0 hasta q1 y q2, por ultimo q2 pasa un cero a q1 terminando el proceso.

4. Muestre el diagrama de Moore generado en JFLAP y en VAS

JFLAP:

Para el VAS no lo he podido descargar

Identifique la ER asociada al nuevo diseño y compárela con la expresión regular simplificada (es decir analícelas con dos cadenas válidas y con dos no válidas). Para ello debe identificar en una tabla la jerarquía de operadores regulares, identificando con colores las sentencias matemáticas

ER para el AFND: 1*(0+0(0+1)*0)(1+0)*

ER para el AFD: 1*0(0+1)*

...