Kleinste Klasse von Automatenmodellen, deren entsprechende Sprachklasse CFL enthält und gegen (Dis-) Zulassen von Nichtdeterminismus im Modell geschlossen ist

Aus einem Kommentar ging eine interessante Frage hervor. Die Klasse der CFLs (die von PDAs anerkannten Sprachen) ist offensichtlich nicht unter Nichtdeterminismus geschlossen - was ich damit meine, ist, dass deterministische PDAs nicht gleichwertig mit nichtdeterministischen PDAs sind.

Alle CFLs sind jedoch entscheidbar, und in diesem Fall entspricht jedes deterministische TM in seiner Leistung einem nichtdeterministischen TM.

Dies ist eine große Lücke - was ist die kleinste Sprache "über" CFLs, die unter Nichtdeterminismus geschlossen wird?

Der Begriff eines PDA kann auf einen verallgemeinert werden$S(n)$ Hilfs-Pushdown-Automat ($S(n)$-AuxPDA) . Es besteht aus

1. ein schreibgeschütztes Eingabeband, umgeben von Endmarkern,
2. eine endliche staatliche Kontrolle,
3. ein Lese- / Schreib-Speicherband mit einer Länge $S(n)$, wo $n$ ist die Länge der Eingabezeichenfolge und
4. ein Stapel

In "Hopcroft / Ullman (1979) Einführung in die Automatentheorie, Sprachen und Berechnung (1. Aufl.) Finden wir:

Satz 14.1 Das Folgende ist äquivalent für$S(n)\geq\log n$.

1. $L$ wird von einem Deterministen akzeptiert $S(n)$-AuxPDA
2. $L$ wird von einem Nichtdeterministen akzeptiert $S(n)$-AuxPDA
3. $L$ ist in $\operatorname{DTIME}(c^{S(n)})$ für eine Konstante $c$.

mit dem überraschenden:

Logische Folge $L$ ist in $\mathsf P$ dann und nur dann, wenn $L$ wird von a akzeptiert $\log n$-AuxPDA.

Der Beweis besteht aus drei Teilen: (1) Wenn L von einem Nichtdeterministen akzeptiert wird $S(n)$-AuxPDA mit $S(n)\geq \log n$, dann $L$ ist in $\operatorname{DTIME}(c^{S(n)})$ für eine Konstante $c$. (2) Wenn$L$ ist in $\operatorname{DTIME}(T(n))$, dann $L$ wird rechtzeitig akzeptiert $T^4(n)$durch ein deterministisches Einband-TM mit einem sehr einfachen Vorwärts-Rückwärts-Kopfabtastmuster (unabhängig von der Eingabe). (3) Wenn$L$ wird rechtzeitig akzeptiert $T(n)$ durch ein deterministisches Einband-TM mit einem sehr einfachen Vorwärts-Rückwärts-Kopfabtastmuster (unabhängig von der Eingabe) $L$ wird von einem Deterministen akzeptiert $\log T(n)$-AuxPDA.

Teil (1) ist im Grunde ein strenger Beweis dafür, dass das "Stoppproblem entscheidbar ist", bei dem die Anzahl der Operationen gründlich gezählt wurde. Teil (2) ist die kreative Idee, die die Bühne für Teil (3) vorbereitet. Teil (3) verwendet den Hilfsspeicher zum Verfolgen des Zeitschritts, der es ermöglicht, die Kopfposition aufgrund des sehr einfachen Vorwärts-Rückwärts-Kopfabtastmusters zu rekonstruieren, und den Stapel zum rekursiven Zurückverfolgen.

Das Obige ist eine Kopie großer Teile einer Antwort auf eine andere Frage . In welchem ​​Sinne beantwortet es die aktuelle Frage? Es ist nicht die kleinste vorstellbare Klasse, die enthält$\mathsf{CFL}$und ist unter Nichtdeterminismus geschlossen. Aber es ist eine sehr bekannte Klasse (dh$\mathsf P$) und ein natürliches Maschinenmodell, das in der Vergangenheit gründlich untersucht wurde und heute noch (mit einer zusätzlichen Laufzeitbeschränkung) im Kontext von LogCFL untersucht wird . In der Tat ist LogCFL auch unter Nichtdeterminismus geschlossen und näher als$\mathsf P$ zu $\mathsf{CFL}$und beweise meinen Standpunkt, dass die oben genannten (dh $\mathsf P$ = $\log n$-AuxPDA) ist nicht die kleinste vorstellbare Klasse dieser Art.