Automatas

APORTE II

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

λ 0 1

Q_0 {Q_0,Q_1}

{Q_0,Q_1}

Q_1 ɸ Q_2

Q_2 Q_2 Q_2

Q_3 Q_4 ɸ

Q_4 Q_4 Q_4

Resuelva

Describa la forma matemática del autómata;

La forma matemática del autómata se expresa de la siguiente manera:

A=[(Q_0,Q_1,〖 Q〗_2, Q_3, Q_4),(0,1), λ,Q_0, (Q_2, Q_4)]

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)

Es una Autómata Finito Determinístico AFD ya que están determinando la ruta por donde puede pasar o correr las cadenas que puede aceptar el autómata.

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.

Σ =(0,1) Es el alfabeto que contiene estos dos símbolos

K=Q_0,Q_1,〖 Q〗_2,Q_3,Q_4 Estados que contiene la autómata

S=Q_0

F=Q_2,Q_4

λ= Σ X K=K, la función de transición indica, a qué estado se va a pasar, teniendo en cuenta cuál es el estado actual y el símbolo que se está leyendo.

Donde la función λ=(Q_0,Q_1,〖 Q〗_2,Q_3,Q_4 )x(0,1)=(Q_0,Q_1,〖 Q〗_2,Q_3,Q_4) viene dada por:

λ=(Q_0,0)=Q_0,Q_3 λ(Q_0,1)=Q_0 Q_1

λ=(Q_1,0)=ɸ λ(Q_1,1)=Q_2

λ=(Q_2,0)=Q_2 λ(Q_2,1)=Q_2

λ=(Q_3,0)=Q_4 λ(Q_3,1)=ɸ

λ=(Q_4,0)=Q_4 λ(Q_4,1)=Q_4

Identifique el lenguaje que genera.

L=(0,1)

El lenguaje que genera según la tabla de transiciones y el diagrama realizado, es una cadena que deben tener dos estados iguales en cualquier parte de la cadena “00” ó “11” y puede empezar la cadena con 0 ó 1. El lenguaje aceptado por esta autómata es:

00

11

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)

Se ingresa la cadena 1001 que es una palabra aceptada

Se inicializa el autómata en Q_0 que es la entrada

La palabra 1001 inicia con un uno (1) el cuál puede tomar dos caminos diferentes uno de ellos es que se queda en el mismo estado y puede realizar el cambio estado a Q_1.

La palabra 1001 continua con un cero (0), el cual la siguiente ruta parte desde el mismo Q_0 que ya que el primer símbolo lo dejo en el estado Q_0 y Q_1 pero la única ruta siguiente posible es desde Q_(0 )a Q_3 ya que en Q_1 no hay transición posible.

La palabra 1001 continua con otro cero (0), desde Q_(3 )hay una transición

al estado Q_4

La palabra 1001 finaliza con un uno (1), desde el mismo Q_4 se da la aceptación

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

JFLAP

VAS

En ambos simuladores se pueden realizar el diagrama de Moore y correr sin ningún problema las cadenas que acepte el autómata, el simulador Vas nos permite generar la tabla de transiciones y pasar un autómata finito no determinísticos (AFND) a un autómata finito determinísticos (AFD), mientras que el simulador JFLAP, es un poco más completo, permitiendo

...