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

...