Schwierigkeit, ein Wort mit einer Länge von höchstens

Problemstellung :

Sei ein (möglicherweise nicht deterministischer) Pushdown-Automat und sei sein Eingabealphabet. Gibt es ein Wort st , das von akzeptiert wird ? $M$ $\cal A$ $w \in \cal A^*$ $|w| \leq k$ $M$

Ist dieses Problem NP-vollständig? Wurde es untersucht? Gibt es einen Algorithmus, mit dem ein solches Wort gefunden werden kann?

cc.complexity-theory np-hardness fl.formal-languages automata-theory Lamine
quelle

Sollte der Algorithmus von Djikstra nicht den Trick machen? (Ich missverstehe hier höchstwahrscheinlich etwas!)

Alpoge

"Länge höchstens "?

k

$k$

Alpoge

Gern geschehen, Kaveh. Ja, ich habe "höchstens" vergessen, ich habe es erneut bearbeitet.

Lamine

Die Antwort ist einfach - ist das eine Hausaufgabenfrage?

Sariel Har-Peled

Haben wir Zugriff auf die Automatenbeschreibung oder haben wir sie nur als Black Box?

Raphael

Antworten:

Berechnen Sie den Schnittpunkt Ihrer CFG-Sprache mit der regulären Sprache (dies bedeutet, die Anzahl der Zustände mit zu multiplizieren und einen "Sackgasse" hinzuzufügen). Überprüfen Sie nun, ob das Ergebnis leer ist: Konvertieren Sie es in eine Grammatik (ich denke, das Ergebnis wird eine Polynomgröße haben) und "backtrack" von Epsilon-Produktionen. $\sum_{i=0}^k A^k$ $k$

Bearbeiten: Kaveh erwähnte, dass dies in Polynom ist. Wenn also als Eingabe angegeben wird, ist der Algorithmus in exponentiell . Kaveh fand jedoch einen Weg, dies zu beheben. Konvertieren Sie den Originalautomaten in ein CFG und ersetzen Sie alle Terminals durch ein festes Terminal. Verwenden Sie nun einen iterativen Algorithmus, um die minimale Größe eines von jedem Nicht-Terminal erzeugten Wortes wie folgt zu ermitteln. $k$ $k$ $|k|$

$\infty$ $A \rightarrow a^t \prod B_i$ $f(A) = \min(f(A),t+\sum f(B_i))$ $O(n)$ $n$

Yuval Filmus
quelle

Ich denke auch, dass die Transformation PDA CFG polynomisch ist. Vielen Dank! So ist das Problem in .

\to

$\rightarrow$

P

$P$

Lamine

Ok, da es eine Möglichkeit gibt, die niedrigste Länge direkt zu berechnen ist keine Eingabe. Aber ich verstehe nicht, warum alle Terminals durch ein festes ersetzt werden. Der Algorithmus sollte mit Originalterminals ordnungsgemäß funktionieren.

| k |

$|k|$

Lamine

Du hast recht, es ist eigentlich egal.

Yuval Filmus

Ändern Sie alle Alphabetzeichen in ein bestimmtes Zeichen. Jetzt haben Sie PDA über ein einzelnes Zeichen definiert. Seine Sprache ist eine kontextfreie Grammatik. Die kontextfreie Grammatik über ein einzelnes Zeichen ist jedoch regelmäßig. Konvertieren Sie also die CFG in eine reguläre Sprache und prüfen Sie, ob sie ein Wort der Länge k enthält.

Nun, all diese Konvertierungen erfordern tendenziell exponentielle Zeit, aber es scheint mir unwahrscheinlich, dass das Problem NP-vollständig ist. Vor allem, wenn Sie die Polynomzeit in zulassen . $k$

Ich könnte mich irren und entschuldige mich für meine erste schnelle Antwort ...

Übrigens folgt die Tatsache, dass eine CFG über einen einzelnen Buchstaben regelmäßig ist, aus dem Satz von Parikh. Obwohl ein direkter Beweis nicht zu schwer ist. Weitere Informationen zum Satz von Parikh finden Sie unter dem Link - es ist ein schönes Ergebnis ... http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf

Sariel Har-Peled
quelle

Nein, ich bin kein Student. Das Problem, das ich erwähnt habe, ist anfangs ein Netzwerkproblem, das als Automat modelliert wurde. Ich würde nur wissen, ob es sich lohnt, nach einer Polynomlösung zu suchen oder nicht.

Lamine

Sollte diese Antwort nicht ein Kommentar sein?

Oleksandr Bondarenko

Ja sollte es. Sariel, könnten Sie dies entweder in einen Kommentar verschieben oder eine Antwort geben?

Suresh Venkat

@Suresh: Sie sind sich dessen vielleicht bewusst, aber jetzt können Moderatoren eine Antwort in einen Kommentar verwandeln .

Tsuyoshi Ito

Ich habe die ursprüngliche Antwort auf einen Kommentar verschoben. Dies ist eine neue Antwort.

Suresh Venkat

Eine wahrscheinlich suboptimale Methode: Führen Sie den Djikstra-Algorithmus aus. Vergleichen Sie dann für jeden Endzustand die Abstände mit . Wenn irgendwelche , akzeptiere. Ablehnen. $k$ $\leq k$

EDIT: Das oben genannte funktioniert nur für NFAs! Das tut mir leid.

Alpoge
quelle

(aber definitiv Poly-Zeit!)

Alpoge

Ich bin nicht sicher, ob der Dijkstra-Algorithmus das Problem lösen kann. Es kann den kürzesten Weg zwischen dem Anfangszustand und dem Endzustand finden. Natürlich kann ein Wort erzeugt werden, das über diese Pfade akzeptiert werden kann. Diese Pfade sind jedoch elementar, und Wörter können über nicht elementare Pfade akzeptiert werden. Andernfalls wäre das Problem, festzustellen, ob eine kontextfreie Grammatik ein Wort erzeugen kann, entscheidbar, ist es aber nicht.

Lamine

Die Prüfung der Leere auf CFLs ist entscheidend, oder?

Alpoge

(Verzeihen Sie mir noch einmal, wenn ich falsch

verstehe

Nun, man kann einen "Markierungs" -Algorithmus verwenden, um dies zu tun (angesichts der CFG) - Terminals markieren, dann Dinge markieren, die Terminals ableiten, dann Dinge markieren, die markierte Dinge ableiten usw., bis der Prozess endet, und dann prüfen wenn die Startvariable markiert ist. Ignorieren Sie auch meine Antwort - das sollten Sie für einen NFA tun (schon gar nicht für einen PDA!).

Alpoge