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

...