Taller Automatas ER a AFND a AFD PDF

Preview

Summary

Ejercicios practicas para identificar y calcular automatas finitos deterministas y no deterministas...

Description

TALLER AUTOMATAS UNIVERSIDAD DE CALDAS CARLOS GUTIERREZ

El algoritmo para convertir expresiones regulares a AFNDs opera construyendo recursivamente el AFND en base a las expresiones regulares particulares. Los AFND a construir son los siguientes

TALLER AUTOMATAS UNIVERSIDAD DE CALDAS CARLOS GUTIERREZ Ejemplo A partir de la ER (b|(b*a)*)a construir al AFND Primero b*

Luego la concatenación con a

Continuamos con el *

Sigue el | o la elección de alternativas

Concatenamos el ultimo simbolo

TALLER AUTOMATAS UNIVERSIDAD DE CALDAS CARLOS GUTIERREZ

Conversión de un AFND a un AFD Definiciones Cerradura épsilon: Dado un AFN definimos la operación cerradura épsilon de un estado X como: C_ε (x) = {x} Ʋ{v | v es alcanzable con transiciones ε a partir de x } Operación Mover: Mover (e, α) = {β| Ǝ una transacción de e con α hacia el estado β} Operación Ir_A: Ir_A (C,α) donde C es un conjunto {e1, e2, e3, en} de estados del AFN y α es un símbolo del alfabeto del mismo AFN. Ir_A (C,α) = C_E(Mover (C ,α))

Ejemplo

C_ε (q5) = {q5} Ʋ{q0,q1,q3} C_ε (q2) = {q2} Ʋ{q3,q1} C_ε (q1) = {q1} Ʋ{λ} C_ε ({q3,q4}) = {q3,q4,q6} Mover (q3,a) = {q4} Mover (q0,a) = {λ} Mover({q5,q1},b) = {q2}

TALLER AUTOMATAS UNIVERSIDAD DE CALDAS CARLOS GUTIERREZ Algoritmo de conversión de un AFN a un AFD 1. Se calcula la C_ε del estado inicial del AFND, el resultado será el estado inicial S0 del AFD (S0 será el estado inicial del AFD y el primer Si del AFD.) 2. Se calcula para cada Si la operación Ir_A para cada α ϵ Σ, la cual arrojara un estado Si (Pudiendo repetirse). 3. Se realiza la operación 2 con todos los estados hasta que ya no surjan estados diferentes.  

El estado inicial del AFD será S0 y los estados finales serán todos aquellos Si que contengan al estado final del AFN original. La función de transición es el resultado de todas las operaciones Ir_A sobre los Si.

Ejemplo Convertir el autómata finito no determinista de la expresión regular (b|b*a)a a un autómata finito determinista.

Se calcula la cerradura épsilon del estado inicial C_ ε (q0)={q0,q1,q2,q3,q5,q8}=A

Alfabeto {a, b}

Se calcula para cada Si la operación Ir_A para cada α ϵ Σ Ir_A(A,a)= C_ ε (Mover(A,a))= C_ ε {q6}={q6,q7,q10}=B Ir_A(A,b)= C_ ε (Mover(A,b))= C_ ε {q4,q9}={q4,q3,q5,q9,q10}=C Ir_A(B,a)= C_ ε (Mover(B,a))= C_ ε {q11}={q11}=D Ir_A(B,b)= C_ ε (Mover(B,b))= C_ ε {λ}={λ} Ir_A(C,a)= C_ ε (Mover(C,a))= C_ ε {q6,q11}={q6,q7,q10,q11}=E Ir_A(C,b)= C_ ε (Mover(C,b))= C_ ε {q4}={q4,q3,q5}=F

TALLER AUTOMATAS UNIVERSIDAD DE CALDAS CARLOS GUTIERREZ Ir_A(D,a)= C_ ε (Mover(D,a))= C_ ε {λ}={λ} Ir_A(D,b)= C_ ε (Mover(D,b))= C_ ε {λ}={λ} Ir_A(E,a)= C_ ε (Mover(E,a))= C_ ε {q11}={q11}=D Ir_A(E,b)= C_ ε (Mover(E,b))= C_ ε {λ}={λ} Ir_A(F,a)= C_ ε (Mover(F,a))= C_ ε {q6}={q6,q7,q10}=B Ir_A(F,b)= C_ ε (Mover(F,b))= C_ ε {q4}={q4,q3,q5}=F • •

El estado inicial es A, ya que originalmente contiene a q0. Los estados finales son D y E ya que contienen a q11.

Tabla de transiciones

TALLER AUTOMATAS UNIVERSIDAD DE CALDAS CARLOS GUTIERREZ

Generar AFND para las siguientes expresiones regulares, convertir a AFD y minimizar por los dos métodos. (determine el alfabeto) 1- a*b 2- (abc)* 3- (b|bc)+ 4- letra(letra|digito)* 5- (a|b)*abb 6- ((b|b*a)*)a 7- (a*|b+)+ 8- (a | b)* abb 9- (a a+ b)+(b*a+)? 10(a+ b c* )(cc)?a+ 11(a (bb)+ c*)b? Dado el alfabeto {a,b,c} realizar la gramatica, convertir a AFND, convertir a AFD y minimizar por los dos métodos 1- gramatica para aceptar palabras que empiecen por dos símbolos del alfabeto y que termine en los mismos símbolos de manera inversa 2- gramatica que acepte un numero impar de a’s o numero múltiplo de tres de b’s 3- gramatica que acepte palabras de tal forma que la vocal simpre este entre dos consonantes 4- gramatica que acepte palabras donde una vocal siempre esta acompañado por una consonante o viceversa 5- gramatica con numero impar de simbolos...