Dureté de trouver un mot de longueur au plus acceptée par un automate pushdown non déterministe

Énoncé du problème:

Soit un automate de refoulement (potentiellement non déterministe) et soit son alphabet d'entrée. Y a-t-il un mot st accepté par ?A w ∈ A ∗ | w | ≤ k $M$$\cal A$$w \in \cal A^*$$|w| \leq k$$M$

Ce problème est-il NP-complet? At-il été étudié? Existe-t-il un algorithme permettant de trouver un tel mot?

Calculez l'intersection de votre langage CFG avec le langage régulier (cela revient à multiplier le nombre d'états par et à ajouter un état "impasse"). Vérifiez maintenant si le résultat est vide: convertissez-le en grammaire (je pense que le résultat aura une taille polynomiale) et "retour en arrière" des productions epsilon.$\sum_{i=0}^k A^k$$k$

Edit: Kaveh a mentionné qu'il s'agit d'un polynôme en , donc si est donné en entrée, l'algorithme est exponentiel en. Cependant, Kaveh a trouvé un moyen de le réparer. Convertissez l'automate d'origine en CFG et remplacez tous les terminaux par un terminal fixe. Utilisez maintenant un algorithme itératif pour trouver la taille minimale d'un mot généré par chaque non-terminal, comme suit.k | k $k$$k$$|k|$

Initialisez toutes les longueurs avec , puis mettez à jour toutes les longueurs de manière évidente: étant donné une production (l'ordre n'a pas d'importance), mettez . Revendication: cela converge en itérations, où est le nombre de non-terminaux. La raison en est que dans un arbre générant le mot de longueur minimale, aucun non-terminal n'est utilisé deux fois; chaque "arête" prend au plus une itération à traiter (certaines arêtes peuvent être "mises à jour" en parallèle).$\infty$$A \rightarrow a^t \prod B_i$O ( n ) $f(A) = \min(f(A),t+\sum f(B_i))$$O(n)$$n$

Remplacez tous les caractères de l'alphabet par un seul caractère spécifique. Maintenant, vous avez PDA défini sur un seul caractère. Son langage est une grammaire sans contexte. Cependant, la grammaire sans contexte sur un seul caractère est régulière. Donc, convertissez le CFG dans un langage normal, puis vérifiez s'il contient un mot de longueur k.

Maintenant, toutes ces conversions nécessitent généralement un temps exponentiel, mais il me semble peu probable que le problème soit NP complet. Surtout si vous autorisez le temps polynomial en .$k$

Je me trompe peut-être, et je m'excuse pour ma réponse snippy initiale ...

BTW, le fait qu'un CFG sur une seule lettre soit régulier découle du théorème de Parikh. Bien qu'une preuve directe ne soit pas trop difficile. Voir le lien pour plus de détails sur le théorème de Parikh - c'est un beau résultat ... http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf

Une méthode probablement sous-optimale: exécutez l'algorithme de Djikstra. Ensuite, pour chaque état final, comparez les distances avec . S'il y en a , acceptez. Rejeter.≤ $k$$\leq k$

EDIT: ce qui précède ne fonctionne que pour les NFA! Désolé pour ça.