Estou trabalhando em um problema definido para uma classe e pensei em uma pergunta relacionada ao que eu estava trabalhando. Existe um número mínimo de estados que um autômato finito deve ter para aceitar cadeias binárias que representam números divisíveis por um número inteiro n? Em um conjunto de problemas anterior, eu era capaz de construir um DFA que aceitava cadeias binárias divisíveis por 3 e 3 estados. Isso é uma coincidência ou existe algo inerente ao problema geral de detectar cadeias divisíveis por n que sugere um número mínimo de estados?
Eu prometo que isso não vai responder uma pergunta de lição de casa para mim! :)
automata-theory
Nick Van Hoogenstyn
fonte
fonte
Respostas:
Existe uma fórmula conhecida para o número mínimo de estados para um autômato finito. Isso depende de , bem como da raiz da representação posicional subjacente.n R
Se é coprime para , então o número mínimo de estados é . No entanto, quando compartilha um fator com a raiz, a situação é bastante complicada. Ver Mathematica Journal Vol. 3, edição 11. "Divisibilidade e complexidade do estado", de Klaus Sutner.n R n n
fonte
Há outro artigo sobre o mesmo assunto: B. Alexeev, DFA mínimo para testar a divisibilidade, J. Comput. Syst. Sci. 69 (2004), 235-243.
fonte