Autómatas finitos que aceptan cadenas binarias divisibles por n

18

Estoy trabajando en un conjunto de problemas para una clase, y pensé en una pregunta relacionada con lo que estaba trabajando. ¿Existe un número mínimo de estados que debe tener un autómata finito para aceptar cadenas binarias que representan números divisibles por un entero n? En un conjunto de problemas anterior, pude construir un DFA que aceptaba cadenas binarias divisibles por 3 con 3 estados. ¿Es una coincidencia, o hay algo inherente al problema general de detectar cadenas divisibles por n que sugiere un número mínimo de estados?

¡Prometo que esto no responderá una pregunta de tarea para mí! :)

automata-theory Nick Van Hoogenstyn
fuente
3
Bienvenido a cstheory, un sitio de preguntas y respuestas para preguntas de nivel de investigación en informática teórica (TCS). Su pregunta no parece ser una pregunta de nivel de investigación en TCS. Consulte las preguntas frecuentes para obtener más información sobre lo que se entiende por esto y sugerencias para los sitios que podrían recibir su pregunta. Finalmente, si su pregunta está cerrada por estar fuera de alcance, y cree que puede editarla para que sea una pregunta de nivel de investigación, no dude en hacerlo. El cierre no es permanente y las preguntas se pueden volver a abrir, consulte las Preguntas frecuentes para obtener más información.
Kaveh
2
@Kaveh: Creo que la pregunta está bien, especialmente dada la respuesta concisa de David.
Huck Bennett
2
@HuckBennett Estoy de acuerdo con Kaveh en que esta pregunta debe cerrarse en teoría, principalmente para ser coherente. Sin embargo, también estoy de acuerdo con usted: esta es una pregunta divertida y cuando vea los DFA por primera vez, definitivamente debería preguntarse. Creo que el OP debería intentar divertirse resolviendo la respuesta por sí mismo, y luego consultar matemáticas para obtener más información.
Artem Kaznatcheev
11
Esta no es tarea (aunque está inspirada en una pregunta de tarea), es una pregunta interesante, no creo que sea un resultado bien conocido y la respuesta a la pregunta apareció en una revista de investigación. No veo por qué debería estar cerrado. El límite superior era tarea, y de hecho es fácil, pero la pregunta era sobre el límite inferior.
Peter Shor
1
@ Janoma: De hecho. El final de la pregunta sugiere que el OP confunde los límites superiores con los límites inferiores.
Michael Blondin

Respuestas:

32

Existe una fórmula conocida para el número mínimo de estados para un autómata tan finito. Esto depende de , así como de la raíz R de la representación posicional subyacente.norteR

Si es coprimo a R , entonces el número mínimo de estados es n . Sin embargo, cuando n comparte un factor con la raíz, la situación es bastante complicada. Ver Mathematica Journal Vol. 3, número 11. "Divisibilidad y complejidad del estado" por Klaus Sutner.norteRnortenorte

David Harris
fuente
1
Exactamente el tipo de cosas que estaba buscando. Gracias, pronto me sumergiré en el periódico.
Nick Van Hoogenstyn
2
El enlace parece roto
gigabytes
8

Hay otro artículo sobre el mismo tema: B. Alexeev, DFA mínimo para probar la divisibilidad, J. Comput. Syst. Sci. 69 (2004), 235–243.

Jeffrey Shallit
fuente