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:

...