Automates finis acceptant des chaînes binaires divisibles par n

Je travaille sur un problème posé pour une classe et j'ai pensé à une question liée à ce sur quoi je travaillais. Existe-t-il un nombre minimum d'états qu'un automate fini doit avoir pour accepter des chaînes binaires qui représentent des nombres divisibles par un entier n? Dans un ensemble de problèmes antérieur, j'ai pu construire un DFA qui acceptait des chaînes binaires divisibles par 3 avec 3 états. Est-ce une coïncidence ou y a-t-il quelque chose d'inhérent au problème général de détection de chaînes divisibles par n qui suggère un nombre minimum d'états?

Je promets que cela ne répondra pas à une question de devoirs pour moi! :)

automata-theory Nick Van Hoogenstyn
la source

Bienvenue sur cstheory, un site de questions / réponses pour les questions de recherche en informatique théorique (TCS). Votre question ne semble pas être une question de niveau recherche dans TCS. Veuillez consulter la FAQ pour plus d'informations sur ce que cela signifie et des suggestions de sites susceptibles d'accueillir votre question. Enfin, si votre question est fermée pour être hors de portée et que vous pensez que vous pouvez la modifier pour en faire une question de niveau recherche, n'hésitez pas à le faire. La fermeture n'est pas permanente et les questions peuvent être rouvertes, consultez la FAQ pour plus d'informations.

Kaveh

@Kaveh: Je pense que la question est correcte, surtout compte tenu de la réponse concise de David.

Huck Bennett

@HuckBennett Je suis d'accord avec Kaveh que cette question devrait être fermée sur cstheory, principalement pour être cohérente. Cependant, je suis également d'accord avec vous: c'est une question amusante et lorsque vous voyez les DFA pour la première fois, c'est certainement une question que vous devriez vous poser. Je pense que l'OP devrait essayer de s'amuser à trouver la réponse par lui-même, puis consulter math.SE pour plus d'informations.

Artem Kaznatcheev

Ce n'est pas des devoirs (bien qu'il soit inspiré d'une question de devoirs), c'est une question intéressante, je ne pense pas que ce soit un résultat bien connu et la réponse à la question est apparue dans un journal de recherche. Je ne vois pas pourquoi il devrait être fermé. La limite supérieure était des devoirs, et est en effet facile, mais la question concernait la limite inférieure.

Peter Shor

@Janoma: En effet. La fin de la question suggère que l'OP confond les bornes supérieures avec les bornes inférieures.

Michael Blondin

Automates finis acceptant des chaînes binaires divisibles par n

Réponses: