Maschinen für kontextfreie Sprachen, die durch Nichtdeterminismus keine zusätzliche Kraft erhalten

21

Bei der Betrachtung von Rechenmodellen für Maschinen wird die Chomsky-Hierarchie normalerweise durch (in der Reihenfolge) endliche Automaten, Push-down-Automaten, linear gebundene Automaten und Turing-Maschinen charakterisiert.

Für die erste und letzte Ebene 1 (reguläre Sprachen und rekursiv aufzählbare Sprachen) spielt es für die Leistungsfähigkeit des Modells keine Rolle, ob deterministische oder nicht deterministische Maschinen betrachtet werden, dh DFAs sind NFAs und DTMs sind NTMs 2 äquivalent .

Bei PDAs und LBAs ist die Situation jedoch anders. Deterministische PDAs erkennen einen streng kleineren Satz von Sprachen als nicht deterministische PDAs. Es ist auch eine bedeutende offene Frage, ob deterministische LBAs genauso leistungsfähig sind wie nicht deterministische LBAs oder nicht [1].

Dies veranlasst meine Frage:

Gibt es ein Maschinenmodell, das die kontextfreien Sprachen charakterisiert, für das der Nichtdeterminismus keine zusätzliche Kraft hinzufügt? (Wenn nicht, gibt es eine Eigenschaft von CFLs, die einen Grund dafür vorschlägt?)

Es erscheint mir unwahrscheinlich, dass es beweisbar ist, dass kontextfreie Sprachen irgendwie Nichtdeterminismus brauchen , aber es scheint kein (bekanntes) Maschinenmodell zu geben, für das deterministische Maschinen ausreichen.

Die Erweiterungsfrage ist dieselbe, jedoch für kontextsensitive Sprachen.

Verweise

  1. S.-Y. Kuroda, "Klassen von Sprachen und linear gebundenen Automaten" , Information and Control, 7: 207-223, 1964.

Fußnoten

  1. Nebenfrage für die Kommentare: Gibt es einen Grund dafür, dass die Ebenen (sortiert nach Mengeneinschluss) der Chomsky-Hierarchie die Nummern 3 bis 0 anstelle von 0 bis 3 haben?
  2. Um es klar auszudrücken, ich spreche von den Sprachen, die nur erkannt werden können. Offensichtlich sind Fragen der Komplexität von einer solchen Änderung radikal betroffen.
formal-languages computability context-free computation-models context-sensitive Luke Mathieson
quelle
1
Sie fragen also nach einer Klasse von Sprachen, die größer als (aber so nah wie möglich) CFLs ist, für die die deterministische Version = die nicht deterministische Version ist?
Ryan
@Ryan Nein, ich frage, ob es ein Maschinenmodell gibt, das die CFLs charakterisiert, für das jedoch nichtdeterministische und deterministische Varianten äquivalent sind. Vorausgesetzt, es gibt keine positive Antwort (von der ich vermute, dass es keine gibt), ist das eine gute Zusatzfrage.
Luke Mathieson
3
Ich denke, das Hauptproblem bei der Frage ist das Fehlen einer allgemeinen Definition für ein "Rechenmodell". Sie können beispielsweise ein deterministisches TM definieren, das mit einem kontextfreien Grammatikprogramm ausgestattet ist, das ein Wort akzeptiert, wenn die Grammatik es generiert. Dies ist ein deterministisches Modell, das CFL entspricht, aber es ist albern ...
Shaull
@Shaull, das ist ein fairer Punkt, aber es scheint schwierig zu sein, eine Definition für ein "vernünftiges" Modell zu geben. Ihr Beispiel fühlt sich offensichtlich unnatürlich an, aber ich glaube nicht, dass es einen vertretbaren Definitionsweg gibt.
Luke Mathieson
Um Ryans Anschlussfrage zu beantworten , würde die in Thomas Klimpels Antwort erwähnte Maschine (obwohl sie nicht so elegant wie ein PDA ist) der Vorstellung von "natürlich" in einer Weise entsprechen, die ein TM, das auf die Berechnung eines CFG beschränkt ist, nicht erfüllen würde. Vielleicht ist die Intuition, dass ein TM mit einer CFG explizit in der Definition einer CFL kodiert, während es beispielsweise nicht offensichtlich ist, dass CFGs und PDAs zusammenhängen sollten, der PDA eine natürliche Erweiterung von DFAs ist und zufällig für CFLs funktioniert .
Luke Mathieson

Antworten:

-2

Nach meinem Verständnis der Berechnungstheorie liegt die einzige Situation, in der der Nichtdeterminismus keine zusätzliche Flexibilität (dh Potenz) bietet, auf der rekursiv aufzählbaren / rekursiven Ebene. Dies ist in erster Linie auf das Problem des Anhaltens und die Einschränkungen der Entscheidbarkeit des TM zurückzuführen. Ich glaube, dies beantwortet eine Ihrer Fragen in den Fußnoten sowie eine Seitenleiste. Die Chomsky-Hierarchie ist eine logische Darstellung der Erhöhung der letztgenannten Flexibilität (wenn ich sagen darf), um der Maschine mehr Leistung zu ermöglichen. Hilft das bei deinen Fragen / Gedanken?

Was die PDAs und LBAs angeht, werden mir die anderen versierten Leute hier in der Community dabei helfen. Meine Erfahrung war mehr mit TMs und der Theorie, die mit dem höheren (mehr RE) Teil der Hierarchie verbunden ist (zumindest so, wie es gelehrt wird) mein under).

Peter-Linzer-Theorie der Berechnung

https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241/ref=pd_sbs_14_img_0?_encoding=UTF8&psc=1&refRID=6AA9FQJWZZNZDTQ6Z3K4

bmc
quelle
Dies beantwortet die Frage nicht. Dem OP ist bereits bekannt, was Sie geschrieben haben.
Yuval Filmus