Kann eine Turing-Maschine entscheiden, ob eine NFA eine Saite mit einer Primlänge akzeptiert?

Ich möchte wissen, ob das folgende Problem entscheidbar ist:

Instanz: Eine NFA A mit n Zuständen

Frage: Gibt es eine Primzahl p, so dass A eine Zeichenkette der Länge p akzeptiert?

Meiner Meinung nach ist dieses Problem nicht zu entscheiden, aber ich kann es nicht beweisen. Der Entscheider kann leicht einen Algorithmus haben, um herauszufinden, ob eine bestimmte Zahl eine Primzahl ist, aber ich verstehe nicht, wie er die NFA detailliert genug analysieren kann, um genau zu wissen, welche Längen sie produzieren kann. Es könnte anfangen, Zeichenfolgen mit dem NFA zu testen, aber für eine unendliche Sprache wird es möglicherweise niemals angehalten (und ist daher kein Entscheider).

Das NFA kann natürlich leicht in ein DFA oder einen regulären Ausdruck geändert werden, wenn die Lösung dies benötigt.

Diese Frage habe ich mir überlegt, um mich auf ein Finale vorzubereiten, das in zwei Wochen ansteht.

computability finite-automata Ausruhen
quelle

Ich bin mir nicht sicher, ob dies ein Undergrad-Level ist, also mach dir keine Sorgen, es zu löschen. Es könnte sich als schweres Problem herausstellen, siehe z. B. terrytao.wordpress.com/2007/05/25/…

Nun, ich habe es erfunden, also kann es schwierig sein. Ich habe keine Beweise für unentscheidbare Probleme mit NFAs / DFAs gefunden, weshalb ich dachte, es könnte interessant sein, einen zu versuchen.

Ich glaube, was Sie damit verbunden haben, ist ein anderes (einfacheres) Problem. Es kann antworten: "Wie viele Zeichenfolgen der Länge x akzeptiert eine NFA?". Mit der angegebenen Formel müssten wir unendlich viele Instanzen von überprüfen, um , ob eine von der NFA akzeptierte Zeichenfolge mit der Länge einer Primzahl vorhanden ist. Ich frage nicht nach einer bestimmten Primzahl, ich frage nach allen.

s_{L} (n)

$s_L(n)$

Antworten:

$a + b k$ $\gcd(a, b) = 1$

Wenn Sie das Obige zusammenfassen, erhalten Sie einen Algorithmus, mit dem Sie überprüfen können, ob Ihre reguläre (oder sogar kontextfreie) Sprache Zeichenfolgen mit Primlänge enthält. Auf jeden Fall keine einfache Frage, IMVHO ...

vonbrand
quelle

Ich wäre Ihnen dankbar, wenn Sie uns dabei helfen könnten, den Satz von Parikh in diesem Fall zu verstehen. Wir können natürlich einen NFA in einen PDA verwandeln, indem wir den Stapel im PDA einfach nicht verwenden. Geben die linearen Teilmengen die Zyklen an? Wenn ja, wie funktioniert das?

Chill

@ Hill, Betrachten Sie einen Pfad durch das DFA. Es kann direkt vom Startzustand in den Endzustand übergehen oder eine Schleife ausführen. Die möglichen Längen von Ketten werden durch den "geraden Teil" + eine Summe von

mal "Länge einer möglichen Schleife" für willkürliches

. Zeichnen Sie einfach ein Gewirr aus einem DFA und zeichnen Sie die Pfade durch. Sie werden sehen, dass die möglichen Längen in Familien von arithmetischen Folgen fallen, die durch die Zyklen definiert werden, dh sie bilden eine semilineare Menge. Keine Notwendigkeit, kontextfrei zu werden (nur ein netter Gratisbonus).

k

$k$

k

$k$

Vonbrand

Ich denke, das beantwortet meine Frage. Ich werde versuchen, mehr über Parikhs Theorem zu erfahren. Ich verstehe die Idee davon und wie es in diesem Fall Zyklen spezifizieren kann. Was ich herausfinden möchte, ist eine "praktische" Lösung, bei der ich einen tatsächlichen Algorithmus zur Lösung dieses Problems erstelle.

Chill

@ Hill, schau dir einfach meinen vorherigen Kommentar an. Es ist nicht so schwer, eine Beschreibung der möglichen Längen zu finden, indem Sie einfach die Symbole auf dem DFA als Diagramm löschen und nach Wegen zwischen dem Start-Start-Status und dem End-Status suchen. Schwer zu formalisieren, für jedes gegebene Beispiel einfach per Hand herauszufinden.

vonbrand

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

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