Autómatas finitos deterministas
AFD para binarios divisibles por 3
Construir un autómata finito determinista que acepte L = { w ∈ {0,1}* : w es la representación binaria de un número divisible por 3 }.
- 1 Estados = residuos módulo 3
Usamos tres estados q0, q1, q2, donde qi significa «el prefijo leído ≡ i (mod 3)». El estado inicial y el único de aceptación es q0.
- 2 Transición al leer un bit
Leer un bit b multiplica el valor por 2 y suma b, así que el nuevo residuo es (2·i + b) mod 3. Esto determina completamente δ.
- 3 Tabla de transición δ
δ(q0,0)=q0, δ(q0,1)=q1 · δ(q1,0)=q2, δ(q1,1)=q0 · δ(q2,0)=q1, δ(q2,1)=q2.
Solución
M = ({q0,q1,q2}, {0,1}, δ, q0, {q0}). Acepta ε, 0, 11, 110, 1001, … (0, 3, 6, 9 en decimal) y rechaza 1, 10, 100 (1, 2, 4).