Guia de Autómatas Finitos Deterministas (AFD) Parte1

Esta es una guía sobre autómatas finitos deterministas que trabajé hace un tiempo con mis estudiantes en la asignatura “Compiladores”, son varios ejemplos que te permitirán comprender el funcionamiento de Autómatas Finitos Deterministas (AFD), los ejemplos tienen como finalidad lo siguiente:

• Evaluar el nivel de comprensión de los AFD.
• Encontrar los elementos (A,S,F,q₀,q₁) del autómata partiendo del diagrama.
• Crear la tabla de transición partiendo del diagrama.
•  Identificar cuando un AF es o no determinista.

Autómatas Finitos Deterministas (AFD). Parte I

Como lecturas adicionales he publicado en los siguientes enlaces temas relacionados:

Analisis Lexico, Tabla de Transiciones

Diagrama de Transición (Autómatas)

Ejemplos de Autómatas

Mini manual de JFlap

 

PARTE I: En esta primera parte el objetivo es poder comprender cuales son los símbolos de entrada, aceptación y de estado, también a partir del diagrama crear la tabla de transición.

EJEMPLO 1: A partir del siguiente diagrama

Determine: Los símbolos de entrada             A Los estados del diagrama            S Los estados de aceptación           F El estado inicial                           q1 Ejemplifique gramáticas válidas
SOLUCIÓN: A = {a, b} S = {q0, q1, q2} F = {q0, q1} q1 = {q0} Gramáticas validas: aaaa, aba, a, bab, bababab

EJEMPLO 2: A partir del siguiente diagrama determine:

Determine: Los símbolos de entrada              A Los estados del diagrama             S Los estados de aceptación            F El estado inicial                            q1 Ejemplifique gramáticas válidas
SOLUCIÓN: A = {a, b, c} S = {q0, q1, q2} F = {q0} q1 = {q0} Gramáticas validas: abb, aca, cacbaca, bbbaa, baccaaa

EJEMPLO 3: A partir del siguiente diagrama construya la tabla de transiciones y determine los siguientes datos.

Determine: Los símbolos de entrada              A Los estados del diagrama            S Los estados de aceptación           F El estado inicial                           q1 Ejemplifique gramáticas válidas
SOLUCIÓN: A = {a, b, c} S = {0, 1,2,3,4,5} F = {1,4,5} q1 = {0} ESTADOS ENTRADA DE DATOS a b C 0 1 3 5 1 - 2 - 2 - 1 - 3 - - 4 4 - - - 5 - - -

EJEMPLO 4: Construya una tabla de transiciones a partir del siguiente diagrama y escriba símbolos reconocidos por el autómata.

SOLUCIÓN: ESTADOS ENTRADA DE DATOS 0 1 1 2 2 2 - 2

EJEMPLO 5: Construya una tabla de transiciones a partir del siguiente diagrama y escriba símbolos reconocidos por el autómata.

SOLUCIÓN: ESTADOS ENTRADA DE DATOS letra : Digito = 1 2 3 5 - 2 2 - 2 - 3 - - - 4 4 - - - - 5 - - 5 -

EJEMPLO 6: Construya una tabla de transiciones a partir del siguiente diagrama y escriba un analizador léxico basado en esa tabla.

Gramática valida

Digito, digito, digito

[0-1][0-1][0-1]*    OK

Tabla de transiciones

ESTADOS	ENTRADA DE DATOS
	digito
1	3
3	4
4	4

EJEMPLO 7: Dado el siguiente diagrama de transiciones obtener A, S, f, qi, F y decir que lenguaje se genera.

Obtener A, S, f, qi, F

A = {a, b}

S = {q₀, q_1, q_2,q₃,q₄}

F = {q_2,q_3,q₄}

q1 = {q₀}

Tabla de transición

ESTADOS	ENTRADA DE DATOS
	a	b
q0	q1, q4	q3
q1	q1	q2
q2	-	-
q3	-	-
q4	-	q4

Lenguaje que genera:

A(a/b)*

a/b*

b

EJEMPLO 8: Dado el siguiente diagrama de transiciones obtener A, S, f, qi, F y decir que lenguaje se genera.

Obtener A, S, f, qi, F

A = {a, b}

S = {q0, q1, q2,q3}

F = {q2}

q1 = {q0}

Tabla de transición

ESTADOS	ENTRADA DE DATOS
	a	b
q0	q1	q3
q1	q3	q2
q2	q1	q3
q3	q3	q3

Lenguaje que genera:

A(a/b)

EJEMPLO 9: El siguiente diagrama, ¿Es un diagrama de transición correspondiente a un AFD? ¿Por qué si o porque no?

No es AFD porque existe más de una transición, con el mismo símbolo de entrada (el símbolo a sale de q_{0 a} q₁ pero también se retorna a q₀), ya que por ello se caracterizan los autómatas finitos no deterministas.