Guia de Autómatas Finitos Deterministas (AFD) Parte2

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 los AFD, los ejemplos tienen como finalidad lo siguiente:

• Crear los AFD partiendo de la tabla de transiciones
• Crear tablas de transiciones partiendo de los AFD
• Crear los AFD a partir de un planteamiento específico.

Autómatas Finitos Deterministas (AFD). Parte II

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

 

Y principalmente la parte 1 publicada en el siguiente enlace:

Guia de Autómatas Finitos Deterministas (AFD) Parte1

PARTE II: En esta primera parte el objetivo es poder crear diagrama de transición a partir de las  tablas de transición.

EJEMPLO 10: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

A = {a, b, c}, símbolo de entrada

S = {q0, q1, q2, q3}, estados

qi = q0 Estado inicial

F = {q0, q1}, estados de aceptación

La función de estado próximo F: s*a, s  definida por la siguiente tabla:

f	A
	a	b	C
q0	q1	q3	q2
q1	q1	q3	q0
q2	q3	q0	q1
q3		q2	q1

SOLUCIÓN: Diagrama de transición

EJEMPLO 11: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

Sea M=(A, S, f, qi, F) dónde:

A = {a, b}

S = {q0, q1, q2}

qi = q0

F = {q0}

f  = se define en la tabla siguiente:

f	A
	a	b
q0	q1	q2
q1	q2	q0
q2	q2	q2

SOLUCIÓN: Diagrama de transición

EJEMPLO 12: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

Sea M=(A, S, f, qi, F) dónde:

A= {0, 1}

S= {q0, q1, q2, q3}

qi= q0

F= {q0}

f = se define en la tabla siguiente:

f	A
	0	1
q0	q2	q1
q1	q3	q0
q2	q0	q3
q3	q1	q2

SOLUCIÓN: Diagrama de transición

EJEMPLO 13: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

Sea M=(A, S, f, qi, F) dónde:

A={a, b}

S={q0, q1}

qi = q0

F= {q0}

F se define en la siguiente tabla.

f	A
	a	b
q0	q0	q1
q1	q1	q0

SOLUCIÓN: Diagrama de transición

 

EJEMPLO 14: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

Sea M=(A, S, f, qi, F) dónde:

A={a, b}

S={q0, q1, q2, q3}

qi = q0

F= {q0, q1, q2}

f se define en la siguiente tabla.

f	A
	a	b
q0	q0	q1
q1	q0	q2
q2	q0	q3
q3	q3	q3

SOLUCIÓN: Diagrama de transición

EJEMPLO 15: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

Sea M=(A, S, f, qi, F) dónde:

A = {a, b}

S = {q0, q1, q2}

qi = q0

F = {q0}

f  dada en la siguiente tabla:

f	A
	a	b
q0	q1	0
q1	0	q0, q2
q2	q0	0

SOLUCIÓN: Diagrama de transición

EJEMPLO 16: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

qi = q0

F ={q2, q4}

A = {a, b}

S = {q0, q1, q2, q3, q4}

f	A
	a	b
q0	q0, q3	q0, q1
q1	0	q2
q2	q2	q2
q3	q4	0
q4	q4	q4

SOLUCIÓN: Diagrama de transición

EJEMPLO 17: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

Sea M el AFN dado por:

A = {a, b}

S = {q0, q1}

qi = q0

F ={q1}

f dada en la siguiente tabla

Determinar si a²b, ba y b²a están en L(M).

f	A
	a	b
q0	q0, q1	q1
q1	0	q0, q1

SOLUCIÓN: Diagrama de transición

EJEMPLO 18: Realice el diagrama de moore correspondiente a partir de los siguientes datos.

A = {a, b}

S = {q0, q1, q2, q3}

qi = q0

F = {q1, q2}

f	A
	a	b
q0	q1	q2
q1	q3	q1
q2	q2	q3
q3	q3	q3

SOLUCIÓN: Diagrama de transición

EJEMPLO 19: Construya un AFD M con símbolos de entrada b que acepte solamente aquellas cadenas con bbb.

SOLUCION:

EJEMPLO 20: Construir un AFD que reconozca números binarios múltiplos de 5. Por ejemplo, debe reconocer:

0, 101, 1010, 1111, 10100

SOLUCION:

EJEMPLO 21: Construya un AF M con símbolos de entrada a y b que acepte solamente aquellas cadenas con a y b tales que el número de b’s es divisible por 3.  (Sugerencia: se recomiendan 3 estados).

SOLUCION:

EJEMPLO 22: Sean a y b los símbolos de entrada, construya un autómata finito M que acepte precisamente aquellas cadenas en las que aparezcan a³y b⁴.

SOLUCION:

 

EJEMPLO 23: Construya un AF M con símbolos de entrada a y b que acepte solamente aquellas  cadenas con a y b tales que aabb aparezca como una sub-cadena. Ejemplo: baaabbba, babaabba serán aceptables, pero babbaa y aababaa no lo serán.

SOLUCION: