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:

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 a2b, ba y b2a 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 a3y b4.

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:
Loading...