¿Por qué este FSM acepta números binarios divisibles por tres?

Question

Esta máquina de estado finito (FSM) acepta números binarios divisibles por tres. En teoría los estados deben ser iguales al valor $n$ mod $3$ pero, ¿cómo funciona esto para los números binarios?

Lo que no entiendo es cómo se juntan las transiciones porque una nueva entrada "0" o "1" no significa que se acabe de añadir un número fijo al total $n$ .

¿Puede ayudarme a entenderlo?

Gracias de antemano.

Answer 1

Estados $A,B$ y $C$ corresponden a entradas congruentes con $0,1$ y $2$ mod $3$ respectivamente. Supongamos que la entrada hasta ahora representa un múltiplo de $3$ para que estés en estado $A$ . A $0$ multiplica el número actual por $2$ , por lo que sigue siendo un múltiplo de $3$ y todavía estás en el estado $A$ . A $1$ lo multiplica por $2$ y añade $1$ , haciéndola congruente con $1$ mod $3$ y ponerte en estado $B$ .

Si el número actual es congruente con $1$ mod $3$ , estás en el estado $B$ . Una entrada de $0$ duplica el número, haciéndolo congruente con $2$ mod $3$ y llevarte al estado $C$ . Una entrada de $1$ por otro lado, duplica el número, haciéndolo congruente con $2$ mod $3$ y luego añade $1$ , por lo que es un múltiplo de $3$ y enviarte al estado $A$ .

De la misma manera se puede analizar lo que ocurre cuando el número actual es congruente con $2$ mod $3$ y estás en el estado $C$ La duplicación del número hace que sea congruente con $4$ y por lo tanto a $1$ mod $3$ y te lleva al estado $B$ y duplicándolo y añadiendo uno te deja en estado $C$ .

Así, los tres estados están realmente conectados de forma adecuada.

Todo esto se reduce a lo que veo que Ted ha dado en su respuesta: cuando se lee un poco $b$ , estás desplazando el número actual un lugar a la izquierda, lo que lo multiplica por $2$ , y luego se agrega $b$ el FSM imita el efecto de esa operación sobre el residuo del número mod $3$ .

Answer 2

Añadiendo un poco $b$ al final de un número binario multiplica el número existente por dos y luego añade $b$ . El diagrama anterior realiza esa operación módulo 3.

Answer 3

He aquí otro enfoque más pedante:

Que el número $n = \sum_{k=0}^{p-1} d_k 2^k$ . Definir $r_k =2^k \bmod 3$ y observe que $r_k=2$ cuando $k$ es impar, y $r_k = 1$ cuando $k$ es par. Así, $n \bmod 3 = \sum_{k=0}^{p-1} d_k r_k \bmod 3$ Esta es la clave para crear un diagrama de estados, con los dígitos binarios $d_0,...,d_{p-1}$ como entradas.

Para calcular la suma, hay que rastrear la suma existente (módulo 3, por supuesto) y si el índice es impar o par (para saber el valor de $r_k$ ). Por tanto, el espacio de estados es $\{0,1,2\} \times \{odd,even\}$ . Es sencillo crear el diagrama de estados con la aceptación de estados $(0,odd)$ y $(0,even)$ . $$\begin{array}{ccc} \mathbb{state} & \mathbb{next \; state}, d_k=0 &\mathbb{next \; state}, d_k=1 \\ \hline \\ (0, odd) & (0, even) & (1, even) \\ (0, even) & (0, odd) & (2, odd) \\ (1, odd) & (1, even) & (2, even) \\ (1, even) & (1, odd) & (0, odd) \\ (2, odd) & (2, even) & (0, even) \\ (2, even) & (2, odd) & (1, odd) \\ \end{array}$$

El problema es que hay 6 estados, no 3 como en el diagrama anterior. Sin embargo, si aplicamos el Algoritmo de Llenado de Tablas FSM (por ejemplo, véase Hopcroft, Motwani, Ullman, "Introduction to Automata Theory, Languages and Computation") para encontrar estados indistinguibles, encontramos que los siguientes pares son indistinguibles: $\{(0,odd), (0,even)\}$ , $\{(1,odd), (2, even)\}$ , $\{(1,even), (2, odd)\}$ . El FSM resultante es idéntico al FSM anterior, con la identificación del estado $A \sim \{(0,odd), (0,even)\}$ , $B \sim \{(1,odd), (2, even)\}$ y $C \sim \{(1,even), (2, odd)\}$ .

Answer 4

Puedes pensar en ello como una división larga de un número binario entre 11 (3).

Si el número empieza por 0, el resto es 0, y pasamos a la siguiente cifra.

Si el número empieza por 1, el resto es 1, y tenemos que considerar la siguiente cifra, hasta que podamos restar 11 (3). Para ello, pasamos al estado B, "hemos visto 1". Ahora, si vemos el 1 en el estado B, entonces el número empieza por 11, y podemos restar el 11 dejando 0 como resto, por lo que volvemos al estado A.

Si vemos el 0 en el estado B, no podemos quitar el 11 todavía, el resto es 2, y pasamos al estado C, "hemos visto el 10". Ahora el siguiente dígito 0 significa que podemos quitar 11, dejando el resto 1, así que volvemos al estado B, "han visto 1", y si el siguiente dígito es 1, podemos quitar 11, dejando el resto 10 (2), y nos quedamos en el estado C, "han visto 10".