Truco corto para encontrar el número de estados en DFA que acepta un conjunto de todos los números binarios que están modificados por n

Supongamos que tenemos una pregunta:

Que: Construct minimal state DFA that accepts set of all binary no. which is 2 mod 5(say)
Ans: 5 states

Para resolver este tipo de preguntas existe una forma tradicional de construir el DFA respectivo para ese problema. El problema en ese enfoque tradicional es que requiere mucho tiempo y no todas las personas pueden construir DFA perfectamente de una sola vez (lo que conducirá a una respuesta incorrecta). 

Entonces, aquí hay un truco para resolver este tipo de preguntas en solo unos segundos. Siga los pasos que se muestran en el diagrama a continuación y, después de un poco de práctica, estará en la punta de sus dedos.

PASOS: 

1. Si n es impar, entonces el mínimo de estados será n.
2. si n no es par:
   • Compruebe si n es igual al formato 2^k (como 4 = 2^2, 8 = 2^3), donde k es cualquier número entero.
   • si n= 2^k. entonces el número mínimo de estados será k+1.
   • Pero, si no n != 2^k
     • Compruebe si n/2 es impar, entonces los estados mínimos serán n/2+1.
     • Si n/2 es par, divida el número entre 2 una y otra vez hasta obtener un dígito impar, luego agregue el número de veces que se dividió el número para obtener el valor impar [((n/2))/2….impar + m]. El resultado de esa suma será el número mínimo de estados.

EXAMPLE 1: 2 mod 5 where r=2,n=5
SOLUTION:
1. 5 is odd 
    Therefore, ans is 5 states (n states)

EXAMPLE 2: 4 mod 8 where r=4,n=8
SOLUTION:
1. 8 is even (so it can't be n states)
2. check n=2^k format
    8=2^3
    Therefore, ans is 4 states(k+1 states)

EXAMPLE 3: 10 mod 16 where r=10,n=16
SOLUTION:
1. 16 is even (so it can't be n states)
2. 16 != 2^k (so it can't be k+1 states)
3. n/2 is even (16/2=8, so it can't be n/2+1 states)
4. Divide n by 2 till we get odd no and keep a count on how many times we are dividing
    16/2=8 , m=1
    8/2=4 , m=2
    4/2=2 , m=3
    2/2=1 ,m=4   (odd found)
    Therefore answer is 5 states (odd + m states)