En los ejercicios 6 al 10, encuentre los conjuntos I, O y S, el estado inicial y la tabla que define el siguiente estado y las funciones de salida para cada máquina de estado finito.
En los ejercicios 11 al 20, encuentre la cadena de salida para la cadena de entrada que se indica y la máquina de estado finito.
11. abba; ejercicio 1
12. abba; ejercicio 2
13. aabbaba; ejercicio 3
14. aabbcc; ejercicio 4
15. aabaab; ejercicio 5
16. aaa; ejercicio 6
17. aabbabaab; ejercicio 7
18. baaba; ejercicio 8
19. bbababbabaaa; ejercicio 9
20. cacbccbaabac; ejercicio 10
En los ejercicios 21 al 26, diseñe una máquina de estado finito que tenga las propiedades indicadas. La entrada siempre es una cadena de bits.
21. Produce 1 si entra un número par de unos; de otra manera produce 0.
22. Produce 1 si entran k unos, donde k es un múltiplo de 3; de otra manera produce 0.
23. Produce 1 si entran dos unos o más; de otra manera produce 0.
24. Produce 1 cuando ve 101; de otra manera produce 0.
25. Produce 1 cuando ve 101 y en adelante; de otra manera produce 0.
26. Produce 1 cuando ve primero 0 y hasta que ve otro 0; en adelante, produce 0; en el resto de los casos produce 0.
27. Sea α =x1 · · ·xn una cadena de bits. Sea β =y1 · · ·yn, donde
para i=1, . . . , n. Sea . Demuestre que si γ alimenta a la máquina de estado finito de la figura 12.1.4, la salida es el complemento de 2 de α (considere el algoritmo 11.5.16 una descripción del complemento de 2).
28. Demuestre que no existe una máquina de estado finito que reciba una cadena de bits y produzca 1 siempre que el número de unos sea igual al número de ceros en la entrada, y produzca 0 de otra manera.
29. Demuestre que no hay una máquina de estado finito que realice la multiplicación en serie. En particular, demuestre que no hay una máquina de estado finito que alimenta números binarios
Ejemplo: Si existe tal máquina, para multiplicar 101 ×1001 se alimentaría 11,00,10,01,00,00,00,00. El primer par 11 es el par de los bits en la extrema derecha (101, 1001); el segundo par 00 es el siguiente par de bits (101, 1001); y así sucesivamente. Se amortigua la cadena de entrada con cuatro pares 00 —la longitud del número más grande 1001 que debe multiplicarse—. Como 101 ×1001 =101101, se asevera que se obtiene la salida mostrada en la tabla adyacente.
