Quero saber se o seguinte problema é decidível:
Instância: um NFA A com n estados
Pergunta: Existe algum número primo p tal que A aceite alguma sequência de comprimento p.
Minha crença é que esse problema é indecidível, mas não posso provar. O decisor pode facilmente ter um algoritmo para descobrir se um número específico é primo, mas não vejo como seria capaz de analisar o NFA em detalhes suficientes para saber exatamente quanto tempo ele pode produzir. Ele pode começar a testar seqüências de caracteres com o NFA, mas para um idioma infinito, ele nunca pode parar (e, portanto, não é uma decisão).
O NFA pode ser facilmente alterado para um DFA ou expressão regular, se a solução precisar, é claro.
Esta pergunta é algo que eu tenho ponderado como uma pergunta de preparação feita por mim mesma para uma final que eu tenho em duas semanas.
fonte
Respostas:
Os comprimentos das strings aceitas por um DFA formam um conjunto semilinear (como no teorema de Parikh para linguagens livres de contexto), a descrição daquelas não é muito difícil de encontrar (essencialmente separa todos os ciclos possíveis do autômato) e por Teorema de Dirichlet Qualquer progressão aritmética da forma com mcd ( a , b ) = 1 contém uma infinidade de primos.a + b k mcd ( a , b ) = 1
A junção das opções acima fornece um algoritmo para verificar se a sua linguagem comum (ou mesmo sem contexto) contém cadeias de comprimento primo. Definitivamente não é uma pergunta simples, IMVHO ...
fonte