MOMENTO 1

MIGUEL YAMITH PEA

1096952403

FABER YAMID ORTIZ CAICEDO

1032438302

GRUPO: 301405 _20

TUTOR: CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD ANCIONAL ABIERTA Y A DISTANCIA

CURSO AUTMATAS Y LENGUAJES FORMALES

INGENIERIA DE SISTEMAS

MARZO DE 2015

ACTIVIDAD

Dado el siguiente Autmata M Finito: M =(K, , q0, , F) donde:

K = {q0, q1, q2, q3, q4, } = {a,b,c} q 0

Es el estado Inicial F = q3, q4,

Donde la funcin de transicin est dada por: : {q0, q1, q2, q3, q4 } {a,b,c} {q0,

q1, q2, q3, q4 } q0 { q3 , q4, }

(q0, a ) = q1 (q0, ) = q2 (q1, b ) =

q3 (q2 , a ) = q4 (q3, a ) = q1 (q3, c ) =

q2 (q4, b ) = q2

1. Plasme la tabla de transicin. Identifique que tipo de autmata es (AFD o

AFND) y justifique su respuesta. (No se trata de dar el concepto de

determinismo)

Tabla 1: Tabla de transicin

Tabla de transicin

-> 2 # #

El autmata es AFND pues tiene ms de una forma de iniciar su secuencia de cadenas y tiene

ms de un final para las mismas, es decir tiene varias posibles cadenas para ser aceptado.

Inicialmente realizamos la prueba con la cadena de datos a, b que nos indica que el recorrido

de los datos inicia en con el dato valido a, que a su vez recibe el dato b en , y termina

con estos dos datos en .

Ahora iniciamos en el estado inicial con el dato valido b, y consecutivamente al ser vlido

el dato pasamos al estado , ingresamos a siguiendo la direccin de flujo de datos y

tenemos que en el estado final tenemos los datos b, a.

Con lo anterior tendramos las siguientes cadenas validas:

Segn

evidencio no existen ms cadenas validas en este autmata.

Tenemos entonces que el lenguaje de las cadenas que inicien con a,b pueden ser validos es

decir si inicia con c no sera vlido, y deben terminar en a b.

En Expresiones matemticas seria:

L={w {a,b,c }*| w=ab, 0}

2. Identifique los elementos (tupla que es) (Asociadas con los elementos del

autmata del ejercicio propuesto). Debe explicar y describir cada elemento y

la funcin y significado en el autmata. Conceptos y definiciones adicionales.

= (, , 0, , )AutomataFinito

= (0, 1, 2, 3, 4) Estado del automata

= (, , , ) Lenguaje aceptado

= (3, 4) Estado final

0 = Estado incial

El primer elemento de la tupla denotado en el autmata en el presente ejercicio llamado M es el

alfabeto denotado como:

M = (K = {q0, q1, q2, q3, q4,}, = {a, b, c}, q0, F = {q3, q4,})

El alfabeto denotado como K cuyos smbolos son q0, q1, q2, q3, q4, la segunda tupla es un

conjunto de estados denotado como y est compuesto por tres estados a, b, c, la tercer tupla

denota el estado inicial q0 y el quinto elemento o tupla denota como q3, q4, que son los estados

finales.

El K (alfabeto) es una parte del autmata compuesto por smbolos o letras y que ayudan a construir

un lenguaje, los (estados o memorias) son los que me determinan un comportamiento y unas

condiciones dadas a ciertas interacciones que pueden cambiar dependiendo del comportamiento

del autmata, el estado q0 (inicial) es donde inicia la palabra o dato de entrada de la mquina, el

estado q3 y q4 (final) es donde llega o se acepta esa entrada inicial.

3. Identifique el lenguaje que genera.

L (M) = { {a, b, c}* l = (a b)* a + a b (a b)* ( + c (a b)* a)}

Todas las cadenas o palabras pertenecientes a los smbolos a, b, c nicamente, pero de esas

cadenas o palabras sern vlidas nicamente las que terminan en a o en b.

() = { {, , }| = () + ( + ())()} el conjunto de todas las posibles cadenas que empiecen por una sola a ; o que empiecen por una a seguida de una b as ab una vez o muchas veces; o que empiecen por una a seguida de una b as ab una vez o muchas veces seguidas por una c y una a solo una vez as ca, seguido de una b y una a as ba una vez o muchas veces o ninguna vez.

4. Muestre en el simulador (grficamente) como recorre una cadena vlida.

Explique cada secuencia. (No se trata solo de captura las imgenes, estas deben

ser ex0plicaas en pi de pgina o de lo contrario no tienen validez)

Cadena valida seleccionada ()

Como podemos apreciar son 5 estados los que intervienen, 3 smbolos junto a . Lo primero que realizamos es ingresar la cadena valida seleccionada en el simulador para realizar la secuencia

paso a paso.

El objetivo es verificar que la cadena es validad, el estado inicial es cuando hay una transicin lambda permite el cambio de estado sin alterar el estado sino simplemente la posicin que sera ahora estado como lo muestra la imagen de arriba.

Con el cambio de estado se presenta dos posibilidades cuando tiene como salida una . Una posibilidad es desde el estado inicial pasar al estado y la otra posibilidad es desde el estado donde lo ubico el lambda pasar al estado directamente, como lo muestra la imagen de arriba.

Con el cambio de estado y dos posibles rutas cuando tiene como salida una . Una posibilidad es desde el estado pasar al estado y la otra posibilidad es desde el estado pasar al estado nuevamente, como lo muestra la imagen de arriba.

Siguiendo las dos posibles rutas cuando tiene como salida una . La posibilidad es desde el estado pasar al estado y la otra posibilidad es desde el estado pasar al estado , como lo muestra la imagen de arriba.

Con el cambio de estado y dos posibles rutas cuando tiene como salida una . Repiten nuevamente desde el estado pasar al estado y la otra posibilidad es desde el estado pasar al estado nuevamente, como lo muestra la imagen de arriba.

Con el cambio de estado y dos posibles rutas cuando tiene como salida una . Una posibilidad es desde el estado pasar al estado y para la otra posibilidad ya no existira un estado que le permita una salida con el smbolo concluyendo en el estado , por lo tanto solo se continuara realizando el seguimiento a la nica ruta que es viable, como lo representa la imagen de arriba al

mostrar en color rojo el fin de una cadena que no puede ser aceptada para esa ruta en especifica.

Muestra el recorrido exitoso de una cadena que culmina teniendo como salida una . Que pasa desde el estado al estado siendo uno de los dos posibles estados finales junto con . El color verde en la imagen de arriba representa que la cadena es aceptada.

5. 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 ofrezcan uno u otro).

Grafico en JFLAP

No me da la opcion de mostrar la tabla o generar la tabla de transiciones

Automaticamente identifica si el grafico del automata es deterministico o no deterministico

Al momento de cruzar varias transiciones entre dos estados en los cuales si repites caracteres o

simbolos, este me permite repetirlos, ya que si los muestra en el orden de creacion de las

transiciones, aun repitiendose caracteres o simbolos.

Grafico en VAS

Me da la opcion de mostrar la tabla o generar la tabla de transiciones

No identifica automaticamente si el grafico del automata es deterministico o no deterministico, es

manual

Al momento de cruzar varias transiciones entre dos estados en los cuales si repites caracteres o

simbolos, este no me permite repetirlos, ya que si se intenta repetir toma el que ya esta.

a b c

Q0 Q1 0 0 Q2

Q1 0 Q3 0 0

Q2 Q4 0 0 0

Q3 Q1 0 Q2 0

Q4 0 Q2 0 0

6. Encuentre la expresin regular (ER)de forma que la asocie y la halle con el

procedimiento de convertir un AF a ER, Debe quedar plasmado el

procedimiento indicando y asociando los componentes de la ER al autmatas

(diagrama de moore)

Para hallar la expresin regular, solo busque las rutas para llegar a los dos puntos de destino

(q3 y q4), el asterisco significa que hay se repite el nmero de veces necesario. La

expresin regular es:

() + ((())(())) + ()

7. Genere tres cadenas vlidas y dos no vlidas

CADENAS VALIDAS CADENAS NO VALIDAS

abca bac

a cb

abc

8. Plasme las tres cadenas vlidas para cada ER en una tabla (identificando

jerarqua de operadores regulares, identificando colores). Para ello apyese en el

video: http://youtu.be/JZPAHHA2PnE (minuto 14 al 33). O en el video

http://youtu.be/wGTxhnPXcw4

La ER del diagrama es la que se ha escrito anteriormente, esta es la realizada apoyndonos en

solo las condiciones expuestas en el ejercicio planteado, ahora el JFLAP realiza esta conversin

de la siguiente manera y nos da la siguiente ER:

ER: ab(ab)*+(ba+ab(ab)*ca)(ba)*

9. Identifique en la misma tabla por que las dos cadenas seleccionadas no se aceptan

o en qu parte se trunca la jerarqua y orden de los operadores.

Ahora se procede a realizar la tabla:

( b ( (ab)* | a) )* + ( (a ( (ba)* |b) ( c( (ab)* |a))*

Texto ingresado

b ab a baba

a ba b ababababab

A ba b c ab a

En este caso b4 abababababcabababa

b b en este caso no se cumple la regla del ingreso

de datos pues solo se puede ingresar una b una sola

vez.

bbaaabbbabbba

b b en este caso no se cumple la regla del ingreso

de datos pues solo se puede ingresar una b una sola

vez.

bbbbbbbb

C en este

caso el lenguaje nos dice que debe ingresar o bien una

a o una b para realizar el inicio de la cadena y pues

ingresando la c ya no funcionara.

cccccccc

La ER del diagrama es la que se ha escrito anteriormente, esta es la realizada apoyndonos en solo

las condiciones expuestas en el ejercicio planteado, ahora el JFLAP realiza esta conversin de la

siguiente manera y nos da la siguiente ER:

ER: ab(ab)*+(ba+ab(ab)*ca)(ba)*

10. Proponga un diseo de un autmata (solo en diagrama de moore) que reconozca el mismo lenguaje que el autmata de este ejercicio y que tenga como caractersticas que sea un AFD y tenga un solo estado final.

Rta:

Se propone el siguiente diseo en diagrama de moore que ejemplifica el lenguaje ingresado en el

ya propuesto.