Sind alle kontextsensitiven Sprachen entscheidbar?

12

Ich habe die Wikipedia-Definition der kontextsensitiven Sprache durchgearbeitet und Folgendes gefunden:

Jede Kategorie von Sprachen ist eine richtige Untermenge der Kategorie direkt darüber. Jeder Automat und jede Grammatik in jeder Kategorie hat einen entsprechenden Automaten oder eine entsprechende Grammatik in der Kategorie direkt darüber.

Ich konnte sehen, dass der linear begrenzte Automat in der Artikelbestellung direkt unter dem Entscheider liegt. Wenn dies der Fall ist, bedeutet dies, dass jede Berechnung auf einem LBA an einem bestimmten Punkt angehalten wird (da jeder LBA eine Entscheidung wäre). Aber ich habe das Gefühl, dass es einige Berechnungen geben kann, die gleichzeitig auf einem LBA ausgeführt werden können, um niemals anzuhalten. Zum Beispiel können wir eine Berechnung auf LBA schreiben, die würde

  1. Lies das erste Symbol auf dem Band und gehe nach rechts.
  2. Lies das nächste Symbol und gehe zurück nach links.

Diese (nutzlose) Berechnung (die offensichtlich eine LB-Berechnung ist) würde auf unbestimmte Zeit nach links und rechts oszillieren und niemals anhalten und kann daher keine Entscheidung treffen. Wo denke ich falsch?

formal-grammars turing-machines undecidability context-sensitive Bongubj
quelle
1
Eine CSL Die Entscheidung ist unabhängig davon , ob es nicht abbreche LBA: nur hat existieren eine LBA dafür.
Raphael

Antworten:

9

Erstens sind alle kontextsensitiven Sprachen entscheidbar, da sie von einem LBA (wie Sie sagten) akzeptiert werden können und eine Turing-Maschine leistungsfähiger ist als ein LBA.

MM′MM′

A.Schulz
quelle
Wenn diese Antwort noch immer nicht verstanden wurde, schlagen wir vor, dass Sie sich für weitere Erläuterungen auf Folie 3-4 dieser Präsentation beziehen .
Bongubj
0

Ich schlage vor, Sie werfen einen Blick auf dieses Buch: Einführung in Sprachen und die Theorie der Berechnung von John E Martin

Seite 283: Es sind noch Fragen zu kontextsensitiven Sprachen offen, z. B. ob jede CSL von einer deterministischen LBA akzeptiert werden kann oder nicht.

Amir Nikabadi
quelle
Wie beantwortet dies die Frage? Kontextsensitive Sprachen sind alle entscheidbar, unabhängig davon, ob Sie einen deterministischen oder nicht deterministischen linearen Raum benötigen.
Yuval Filmus