Practica 5 TALF

Enunciado practica 5

Autómatas finitos no deterministas

1.- Dado el autómata finito no determinista descrito por la siguiente tabla, obtener el autómata finito determinista y posteriormente minimizarlo. El alfabeto que usa el autómata se compone de los símbolos: ∑ = {a,b}; el estado inicial es q0; y los estados finales q2 y q4.

tabla autómata 1modelamos el autómata en JFlap

autómata sin minimizar 1Ahora es el momento de minimizarlo, primero debemos transformarlo en un AFD. para eso seleccionamos la opción (“Convert to DFA”) del menú Convert.

convirtiendo a AFD

Pinchamos en Complete y finalmente en Done? lo que nos creara un AFD en una nueva ventana.

AFD convertido

Pinchamos en la opción minimize DFA del menú convert para obtener el AFD mínimo

minimizando

Pinchamos en el primer elemento del árbol de estados y pinchamos en el botón “Complete Subtree” para posteriormente pinchar en el botón “finish”

Esto creara una nueva ventana con el conjunto de estados.

conjunto de estados

pinchamos en “complete” para que cree los enlaces

enlaces creados

y finalmente en “done” que nos mostrara una ventana con el AFD minimizado.

AFD minimo

2.- Dado el autómata finito no determinista descrito por la siguiente tabla, obtener el autómata finito determinista y posteriormente minimizarlo. El alfabeto que usa el autómata se compone de los símbolos: ∑ = {0,1}; el estado inicial es q0; y el estado final q1.

tabla autómata 2

modelamos el autómata en JFLAP

lo transformamos en un AFD siguiendo los pasos del ejercicio anterior.

y lo minimizamos igual que en el ejercicio anterior.

Leave a Reply

Your email address will not be published. Required fields are marked *