Une machine de Turing peut-elle décider si un NFA accepte une chaîne de longueur principale?

Je veux savoir si le problème suivant est décidable:

Instance: un NFA A avec n états

Question: Existe-t-il un nombre premier p tel que A accepte une chaîne de longueur p.

Ma conviction est que ce problème est indécidable, mais je ne peux pas le prouver. Le décideur peut facilement avoir un algorithme pour déterminer si un nombre particulier est premier, mais je ne vois pas comment il pourrait analyser le NFA avec suffisamment de détails pour savoir exactement quelles longueurs il peut produire. Il pourrait commencer à tester des chaînes avec le NFA, mais pour un langage infini, il pourrait ne jamais s'arrêter (et donc ne pas être un décideur).

Le NFA peut facilement être changé en DFA ou en expression régulière si la solution en a besoin, bien sûr.

Cette question est quelque chose que j'ai réfléchi en tant que question préparée par moi-même pour une finale que j'arrive dans 2 semaines.

computability finite-automata Refroidissement
la source

Je ne sais pas s'il s'agit d'un niveau de premier cycle, alors ne vous inquiétez pas de le supprimer. Cela pourrait s'avérer être un problème difficile, voir par exemple terrytao.wordpress.com/2007/05/25/…

Eh bien, je l'ai inventé, donc ça pourrait être difficile. Je n'ai trouvé aucune preuve de problèmes indécidables impliquant des NFA / DFA, c'est pourquoi j'ai pensé qu'il pourrait être intéressant d'en essayer un.

Je crois que ce à quoi vous avez lié est un problème différent (plus facile). Il peut répondre "combien de chaînes de longueur x un NFA accepte-t-il?". En utilisant la formule fournie, il faudrait vérifier une infinité d'instances de

pour voir s'il existe une chaîne acceptée par le NFA qui est de longueur première. Je ne pose pas de question sur un nombre premier particulier, je pose des questions sur chacun d'eux.

s_{L} (n)

$s_L(n)$

Réponses:

Les longueurs des chaînes acceptées par un DFA forment un ensemble semi-linéaire (comme dans le théorème de Parikh pour les langues sans contexte), la description de celles-ci n'est pas trop difficile à trouver (essentiellement épisser tous les cycles possibles de l'automate), et par Le théorème de Dirichlet toute progression arithmétique de la forme avec contient une infinité de nombres premiers. $a + b k$ $\gcd(a, b) = 1$

Le fait de rassembler ce qui précède donne un algorithme pour vérifier si votre langage standard (ou même sans contexte) contient des chaînes de longueur principale. Absolument pas une question simple, IMVHO ...

vonbrand
la source

J'apprécierais un peu d'aide pour comprendre le théorème de Parikh dans ce cas. Nous pouvons évidemment transformer un NFA en PDA en n'utilisant tout simplement pas la pile dans le PDA. Les sous-ensembles linéaires spécifient-ils les cycles? Si oui, comment ça marche?

Chill

k

$k$

k

$k$

Je pense que cela répond à ma question. Je vais essayer d'en savoir plus sur le théorème de Parikh. Je comprends l'idée de celui-ci et comment il peut spécifier des cycles dans ce cas. Ce que je veux comprendre, c'est une solution plus "pratique" où je crée un algorithme réel pour résoudre ce problème.

Chill

@Chill, il suffit de regarder mon commentaire précédent. Il n'est pas si difficile de trouver une description des longueurs possibles en effaçant simplement les symboles sur le DFA sous forme de graphique et en vérifiant les marches entre l'état de départ et les états finaux. Difficile à formaliser, facile à comprendre à la main pour un exemple donné.

vonbrand

a a a a (a a)^{*}

$a a a a (a a)^*$