Para cada autómata de estado finito no determinístico en los ejercicios 6 al 10, encuentre los conjuntos I, S, y A, el estado inicial y la tabla que define la función del siguiente estado.
11. Escriba las gramáticas regulares dadas por el autómata de estado finito de los ejercicios 4 al 9, sección 12.2.
12. Represente las gramáticas de los ejercicios 1 y 5, sección 12.3 y el ejemplo 12.3.14 por un autómata de estado finito no determinístico.
13. ¿El autómata de estado finito no determinístico de la figura 12.4.2 acepta la cadena bbabbb? Pruebe su respuesta.
14. ¿El autómata de estado finito no determinístico de la figura 12.4.2 acepta la cadena bbabab? Pruebe su respuesta.
15. Demuestre que una cadena α sobre {a, b} es aceptada por el autómata de estado finito no determinístico de la figura 12.4.2 si y sólo si α contiene exactamente una a y termina con b.
16. ¿La cadena aaabba es aceptada por el autómata de estado finito no determinístico de la figura 12.4.3? Pruebe su respuesta.
17. ¿La cadena aaaab es aceptada por el autómata de estado finito no determinístico de la figura 12.4.3? Pruebe su respuesta.
18. Caracterice las cadenas aceptadas por el autómata de estado finito no determinístico de la figura 12.4.3.
19. Muestre que las cadenas aceptadas por el autómata de estado finito no determinístico del ejercicio 8 son precisamente las cadenas sobre {a, b} que terminan con bab.
20. Caracterice las cadenas aceptadas por el autómata de estado finito no determinístico de los ejercicios 1 al 7, 9 y 10. Diseñe un autómata de estado finito no determinístico que acepte las cadenas sobre {a, b} que tienen las propiedades especificadas en los ejercicios 21 al 29.
21. Comienzan con abb o con ba
22. Terminan con abb o con ba
23. Contienen abb o ba
24. Contienen bab y bb
25. Cada b está precedida y seguida por una a
26. Comienzan con abb y terminan con ab
27. Comienzan con ab pero no terminan con ab
28. No contienen ba ni bbb
29. No contienen abba ni bbb
30. Escriba las gramáticas regulares que generan las cadenas de los ejercicios 21 al 29.
