En los ejercicios 4 al 6, dibuje de nuevo el diagrama del autómata de estado finito como el diagrama de transición de una máquina de estado finito.
En los ejercicios 7 al 9, dibuje el diagrama de transición del autómata de estado finito (I, S, f, A, σ0).
10. Para cada autómata de estado finito en los ejercicios 1 al 6, encuentre los conjuntos I, Sy A, el estado inicial, y la tabla que define la función del siguiente estado.
11. ¿Cuáles de las máquinas de estado finito de los ejercicios 1 al 10, de la sección 12.1, son autómatas de estado finito?
12. ¿Cómo debe verse la tabla de una máquina de estado finito M para que M sea un autómata de estado finito?
En los ejercicios 13 al 17, determine si la cadena que se indica es aceptada por el autómata de estado finito dado.
13. abbaa; figura 12.2.2
14. abbaa; figura 12.2.3
15. aabaabb; figura 12.2.5
16. aaabbbaab; ejercicio 5
17. aaababbab; ejercicio 6
18. Demuestre que el autómata de estado finito de la figura 12.2.2 acepta una cadena α en {a, b} si y sólo si α termina con a.
19. Demuestre que el autómata de estado finito de la figura 12.2.5 acepta una cadena α en {a, b} si y sólo si α termina con bb.
20. Caracterice las cadenas aceptadas por el autómata de estado finito de los ejercicios 1 al 9. En los ejercicios 21 al 31, dibuje el diagrama de transición de un autómata de estado finito que acepte el conjunto dado de cadenas en {a, b}.
21. Número par de símbolos a
22. Exactamente una b
23. Al menos una b
24. Exactamente dos símbolos a
25. Al menos dos símbolos a
26. Contiene m símbolos a, donde m es múltiplo de 3
27. Comienza con baa
28. Contiene abba
29. Toda b va seguida por a
30. Termina con aba
31. Comienza con ab y termina con baa
32. Escriba algoritmos similares al algoritmo 12.2.10, que decidan si los autómatas de estado finito de los ejercicios 1 al 9 aceptan o no una cadena dada.
33. Dé un argumento formal para mostrar que los autómatas de estado finito de las figuras 12.2.6 y 12.2.8 son equivalentes.
34. Sea L un conjunto de cadenas en {a, b}. Demuestre que existe un autómata de estado finito que acepta a L.
35. Sea L el conjunto de cadenas aceptadas por el autómata de estado finito del ejercicio 6. Sea S el conjunto de todas las cadenas en {a, b}. Diseñe un autómata de estado finito que acepte S – L.
36. Sea Li el conjunto de cadenas aceptadas por el autómata de estado finito Ai = (I, Si, fi, Ai, σi), i=1, 2. Sea A= (I, S1 ×S2, f, A, σ), donde f((S1, S2), x) = ( f1(S1, x), f2(S2, x))
A={ (A1, A2) | A1 ∈A1 and A2 ∈A2}
σ = (σ1, σ2).
Demuestre que Ac(A) = L1 ∩L2
37. Sea Li el conjunto de cadenas aceptadas por el autómata de estado finito Ai =(I, Si, fi, Ai, σi), i=1, 2. Sea A= (I, S1 ×S2, f, A, σ),
donde
f((S1, S2), x) = ( f1(S1, x), f2(S2, x))
A={ (A1, A2) | A1 ∈A1 or A2 ∈A2}
σ = (σ1, σ2).
Demuestre que Ac(A) = L1 ∪L2
En los ejercicios 38 al 42, sea Dibuje el diagrama de transición del autómata de estado finito que acepta L1∩L2 y L1 ∪L2.
38. A1 dado en el ejercicio 4; A2 dado en el ejercicio 5
39. A1 dado en el ejercicio 4; A2 dado en el ejercicio 6
40. A1 dado en el ejercicio 5; A2 dado en el ejercicio 6
41. A1 dado en el ejercicio 6; A2 dado en el ejercicio 6
42. A1 dado por la figura 12.5.7, sección 12.5; A2 dado en el ejercicio 6
