Festlegen, ob eine unäre kontextsensitive Sprache regulär ist

Es ist ein bekanntes Ergebnis, dass die Frage

Erzeugt eine kontextfreie Grammatik eine reguläre Sprache?

ist unentscheidbar. Es wird jedoch auf einem unären Alphabet entscheidbar, einfach weil in diesem Fall die Klassen der kontextfreien und regulären Sprachen zusammenfallen.

Meine Frage ist zu wissen, was bei unären kontextsensitiven Sprachen passiert .

Ist es entscheidend zu wissen, ob eine bestimmte kontextsensitive Grammatik auf einem unären Alphabet eine reguläre Sprache erzeugt?

Wenn die Antwort positiv ist, wäre eine Einschätzung der Komplexität zu begrüßen.

Leider ist Ihr Problem nicht zu entscheiden. Der Ansatz, über den ich gestolpert bin (der möglicherweise überarbeitet ist, also sollte jeder, der einen zweckmäßigeren Ansatz hat, vorgehen!), Verwendet zuerst ein diagonales Argument, um zu demonstrieren, dass es eine unäre CSL die nicht regelmäßig ist (im Gegensatz zum positiven Ergebnis) für unäre CFLs) und reduziert dann das Halteproblem für Turing-Maschinen, indem bei gegebenem TM M ein CSG G konstruiert wird, das M auf einer Länge des Bandes simuliert, die kürzer als der Parsing-String w ist , wobei X erkannt wird, wenn M anhält, ohne seine Grenzen zu überschreiten und sonst nicht analysieren, so dass G erfolgreich alle w ∈ X analysiert$X$$M$$G$$M$$w$$X$$M$$G$$w \in X$das sind ausreichend lange, wenn anhält (so dass L ( G ) sich von X nur in endlich vielen Zeichenketten unterscheidet und daher nicht regulär sein kann), sonst erkennt G die leere Sprache (die eindeutig regulär ist).$M$$L(G)$$X$$G$

Der Schlüssel zu diesem Ansatz ist die Beobachtung, dass CSGs sich nicht nur mit grammatikalischen Fragen wie der Phrasenstruktur befassen - CSG-Ableitungssequenzen können in der Tat beliebige nicht deterministische raumbegrenzte Berechnungen durchführen (tatsächlich gibt es $\mathbf{PSPACE}$-complete CSLs), bevor Sie mit der Ausrichtung an der Parsing-Zeichenfolge beginnen. Dies lässt sich am einfachsten durch Standardkonvertierungen zwischen CSGs und monotonen Grammatiken (die weiterhin funktionieren, wenn sie auf unäre Alphabete beschränkt sind) und durch die Verwendung einfacher monotoner Produktionen zur Simulation von Turing-Maschinenübergängen auf Ableitungszeichenfolgen, die Stufen in einem Berechnungsverlauf darstellen, beobachten. In dieser Antwort gehe ich davon aus, dass der Leser die meisten Details verstehen kann, wenn eine CSG erforderlich ist, um eine bestimmte Berechnung zu simulieren. (Ich gehe davon aus, dass der Fragesteller mit all dem vertraut ist, aber ich werde es der Vollständigkeit halber noch einmal durchgehen. Sie können jedoch gerne eine Erläuterung in den Kommentaren anfordern.)

Erstens brauchen wir unsere nicht reguläre unäre CSG. ( EDIT: Also , das war übertrieben - unregelmäßige unäre CSLs können leicht zB über das Pumplemma in jeder Sprache angezeigt werden, die die grundlegendste Unregelmäßigkeit aufweist. Siehe die Kommentare für Beispiele. Im Nachhinein unter Verwendung eines diagonalen Arguments Es war, als würde man einen nuklearen Sprengkopf zu einem Messerkampf bringen. Wenn Sie neugierig sind, lesen Sie diese Konstruktion durch.

Lassen eine Aufzählung von DFAs über dem Alphabet { 1 } sein , so dass die Anzahl von Zuständen in D i in i zunimmt . Wir beschreiben ein CSG G X hinsichtlich seines Verhaltens beim Analysieren von String 1 n ∈ { 1 } ∗ :$D_1, D_2, ...$$\{1\}$$D_i$$i$$G_X$$1^n \in \{1\}^*$

1. Generieren Sie nicht deterministisch eine Zeichenfolge aus "leeren" Nicht-Terminals, die wir als "Band" betrachten. Einer der leeren Nicht-Terminals sollte ein separater Nicht-Terminal "Leerzeichen + Schreib- / Lesekopf + Startstatus" sein. Wenn die Analysezeichenfolge nicht 1 n ist, schlägt diese Ableitung fehl. Wir beschreiben den Rest des Prozesses anhand der deterministischen Berechnung, die durch die einzig mögliche Ableitung simuliert wird.$n$$1^n$
2. Drucken Sie auf das Band eine Kodierung von gefolgt von der Zahl i in binär, wobei i = n - c und c gewählt wird, damit auf dem Band immer genug Platz ist, um das zu tun, was wir brauchen. (Dies ist möglich, da der zum Codieren von D i und i erforderliche Platz logarithmisch in i wächst .)$D_i$$i$$i = n - c$$c$$D_i$$i$$i$
3. am Eingang 1 i auswerten . Dies erfordert kein darstellt D i ‚s Band - Sie einen einzelnen Staat nur speichern können, die Sie entsprechend den Übergängen ändern D i wie Sie verringern i .$D_i$$1^i$$D_i$$D_i$$i$
4. Wenn verwirft 1 i , überschreibt das gesamte Band mit nicht-Terminals , die produzieren 1 . Ansonsten scheitern.$D_i$ $1^i$$1$

Wir nehmen . Es ist klar, dass X ≤ L ( D i ) für jedes i gilt , da 1 i + c ≤ X ≤ 1 i + c ≤ L ( D i ) .$X = L(G_X)$$X \ne L(D_i)$$i$$1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$

Der nächste Schritt besteht darin, eine Reduktion vom Halteproblem zum Fragestellerproblem zu entwerfen. (Wenn Sie den obigen Abschnitt übersprungen haben, sei eine beliebige unregelmäßige unäre CSL, die von CSG G X generiert wird .)$X$$G_X$

Sei ein beliebiges TM. Wir wandeln M in ein CSG G um, das sich bei der Analyse von String 1 n wie folgt verhält :$M$$M$$G$$1^n$

1. Generieren Sie leere Nicht-Terminals, wobei das am weitesten links stehende das separate leere + Schreib- / Lesekopf-Nicht-Terminal ist, und generieren Sie auch eine "Grenze" ohne Terminal auf jeder Seite. Auch hier versagen wir, wenn wir die falsche Anzahl von Nicht-Terminals generieren.$n-2$
2. Simulieren Sie im Raum zwischen den nicht terminalen Begrenzungen. Wenn sich M jemals auf einen der Grenzzustände verschiebt, beenden wir die Simulation und nehmen an, dass M niemals anhält.$M$$M$$M$
3. Wenn stoppt, verhalten sich wie G X . Wenn wir die Simulation beenden mussten, dann scheitern Sie.$M$$G_X$

Beachten Sie, dass, wenn schafft, für immer innerhalb der Grenzen zu laufen, G niemals eine Analysezeichenfolge generieren kann und daher fehlschlägt. Wenn M anhält, gibt es eine gewisse Menge an Raum n, die ausreicht, um die gesamte Berechnung von M zu enthalten. Daher parst G 1 m, wenn m ≥ n + 2 und 1 m ≤ X ist , und daher ist X die Vereinigung von L ( G ). und eine endliche Sprache, aus der L ( G $M$$G$$M$$n$$M$$G$$1^m$$m \ge n+2$$1^m \in X$$X$$L(G)$$L(G)$ist nicht regelmäßig. Wenn andererseits niemals anhält, dann ist L ( G ) = ∅ eindeutig regelmäßig.$M$$L(G) = \varnothing$

Ein Algorithmus zum Entscheiden, ob regulär ist oder nicht, würde bestimmen, ob M auf einem leeren Band anhält oder nicht , was unentscheidbar ist. Daraus folgt, dass das Problem des Fragenden nicht zu entscheiden ist.$L(G)$$M$

Dies ist im Wesentlichen die gleiche Antwort wie oben, aber da nach einer "zweckmäßigeren" Antwort gesucht wird, erwähne ich Folgendes: (Dies ist auch mein erster Beitrag hier, also verzeihen Sie mir, wenn ich eine Kleinigkeit poste!)

Beachten Sie, dass die Leere für unäre kontextsensitive Sprachen unentscheidbar ist. Korrigieren Sie eine kontextsensitive, aber nicht reguläre Sprache . Wenn eine LBA für , kann man leicht eine LBA für konstruieren . Dann ist genau dann regelmäßig, wenn leer ist. L ⊆ a * L ' = { a n | a n ∈ N  und  ∃ m ≤ n : eine m ∈ L } L '$N\subseteq a^*$$L\subseteq a^*$$L'=\{ a^n \mid \text{$a^n\in N$ and $\exists m\le n\colon a^m \in L$}\}$$L'$$L$

Update: Dasselbe Argument zeigt natürlich, dass Unentscheidbarkeit bereits für den deterministischen logarithmischen Raum gilt.