¿Cuántos estados necesita este diseño de paridad?
Par e impar.
El diseño necesita representar las dos situaciones P e I.
Sus respuestas al terminar son distintas: solo P acepta.
Por tanto este diseño usa2 estados y ambos son necesarios para la paridad.
¿Acepta 1100 el autómata de paridad de unos? Sí o no.
Cuenta dos unos o sigue los cambios.
Desde P, los dos primeros unos producen P→I→P.
Los dos ceros restantes mantienen el estado P.
Al terminar1100 está en P y se acepta; la respuesta es sí.
¿Acepta 1? Sí o no.
Un uno cambia a impar.
La ejecución empieza en P.
Como I no es aceptante y ya terminó la entrada,1 se rechaza. La respuesta es no.
DFA completo con 3 estados y alfabeto de 2 símbolos: ¿cuántos pares estado-símbolo debe definir?
Producto cartesiano.
Una función de transición completa debe definir una salida por cada par deQ×Σ.
Hay3 posibilidades para el estado y2 para el símbolo.
El producto3·2=6 es la cantidad de pares, aunque se repitan los estados de destino.
Prueba el invariante del autómata de paridad por inducción en la longitud del prefijo.
Comprueba prefijo vacío y efecto de cada símbolo.
Caso inicial: el prefijo vacío contiene cero unos y la ejecución está en P, por lo que el significado es correcto.
Supongamos correcto el significado tras un prefijo.
Si añadimos0, no cambia la cantidad de unos ni el estado; si añadimos1, cambian la paridad y el estado.
La inducción demuestra el invariante para todos los prefijos y, al terminar, aceptación exactamente en la paridad par.