Welche Bedeutung haben kontextsensitive Sprachen (Typ 1)?

34

Zu sehen, dass in der Chomsky-Hierarchie Sprachen des Typs 3 von einer Zustandsmaschine ohne externen Speicher (dh einem endlichen Automaten), Typ 2 von einer Zustandsmaschine mit einem einzelnen Stapel (dh einem Pushdown-Automaten) und Typ 0 von erkannt werden können Wie passen Sprachen des Typs 1 in dieses Bild, wenn es sich um eine Zustandsmaschine mit zwei Stapeln (oder, wie bei Turing Machines, um ein Band) handelt? Und welche Vorteile bringt es, festzustellen, dass eine Sprache nicht nur Typ 0, sondern Typ 1 ist?

Bitmaske
quelle
2
Da Sie hier und nicht in cstheory.SE nachfragen (wie von @Sunil vorgeschlagen), schlage ich vor, dass Sie auch eine kurze Beschreibung / Definition von Typ 1 hinzufügen, die möglicherweise nicht für alle ein vertrauter Begriff ist.
Janoma
5
@ Sunil Nein, würde es nicht. Dies ist keine Frage auf Forschungsebene (und selbst wenn dies der Fall wäre, wäre es hier immer noch ein Thema, da wir Fragen auf Forschungsebene nicht ausschließen - zumindest erinnere ich mich daran, dass dies das Ergebnis der Diskussion zu area51 war).
6.
3
@Janoma: Warum sollte es hilfreich sein, Informationen aufzunehmen, die einfach nachgeschlagen werden können (würde das nicht als Rauschen gelten)?
Bitmaske
4
@Janoma Ich denke, die allgemeine Richtlinie sollte darin bestehen, Konzepte zu erläutern, die jemandem, der die Frage beantworten könnte, möglicherweise nicht bekannt sind (wenn die Richtlinie alles erklären würde, was einige Benutzer der Website möglicherweise nicht wissen, würden wir alles erläutern die ganze Zeit und das ist sicherlich nicht der Standard auf anderen SE-Sites). Und ich glaube nicht, dass jemand, der die Chomsky-Hierarchie nicht kennt, die Frage beantworten kann. Natürlich tut es nicht weh, so viel wie möglich zu erklären (solange es die Frage nicht langweilig macht) - ich denke nur nicht, dass es in diesem Fall notwendig ist.
6.
4
Jeder Informatik-Major kennt (oder sollte wissen) die Chomsky-Hierarchie. Jeder andere kann es in 20s nachschlagen. Ein Link zu vielleicht Wikipedia sollte hier genügen.
Raphael

Antworten:

19

Die kontextsensitiven Sprachen sind genau die Sprachen, die von einer Turing-Maschine unter Verwendung eines linearen Raums und Nichtdeterminismus erkannt werden können. Sie können eine solche Turing-Maschine mit Hilfe der Exponentialzeit simulieren, sodass Sie jede solche Sprache in Exponentialzeit erkennen können. Beachten Sie, dass das Problem beim Erkennen einiger kontextsensitiver Sprachen vollständig ist. Dies bedeutet, dass Sie mit ziemlicher Sicherheit nicht besser als mit exponentieller Zeit arbeiten können.PSPACE

Wenn Sie dies mit Sprachen des Typs 0 vergleichen, können Sie zumindest sagen , wie lange es dauert, bis die Sprache erkannt wird. Eine Sprache vom Typ 0 kann möglicherweise nicht einmal entschieden werden: Die Sprache aller Turing-Maschinen, die anhalten, ist eine Sprache vom Typ 0, aber da das Erkennen dieser Sprache genau das Problem des Anhaltens ist, kann sie nicht entschieden werden.

Kontextsensitive Grammatiken sind in der Praxis nicht sehr nützlich. Kontext- freie Grammatiken sind intuitiv Arbeit mit, aber wie die Beispiele auf Wikipedia zeigen , kontext- sensitive Grammatiken werden sehr schnell ziemlich chaotisch. Programme, die Polynomial Space verwenden, sind viel einfacher zu entwerfen (und die Vollständigkeit garantiert die Existenz einer äquivalenten CSG, die nur polynomial größer ist als der Speicherplatzbedarf Ihres Algorithmus).PSPACE

Der Grund für ihre Existenz ist, dass sie eine sehr natürliche Erweiterung der kontextfreien Grammatik bilden (Sie erlauben dem Kontext, zu bestimmen, welche Produktionen gültig sind). Dies wird Chomsky wahrscheinlich dazu inspiriert haben, sie zu definieren und als Typ-1-Sprachen zu bezeichnen. Denken Sie daran, dass diese Definition vorgenommen wurde, bevor Computer so schnell wurden wie heute: Es ist für formale Sprachtheoretiker interessanter als für Programmierer.

Uneingeschränkte Grammatik wird noch seltsamer: Es gibt keine Idee mehr, ein Nichtterminal zu erweitern und durch eine Produktion zu ersetzen, möglicherweise abhängig vom Kontext. Sie können den Kontext auch frei ändern. Dies macht das Arbeiten mit uneingeschränkten Grammatiken noch weniger intuitiv: Programme sind gleichwertig und viel intuitiver.

Alex ten Brink
quelle
Aber kontextsensitive Sprachen sind nützlich! Siehe zum Beispiel diese Diskussion .
Raphael
Kontextsensitivität ist nützlich, aber kontextsensitive Grammatiken zur Beschreibung von Sprachen sind IMO nicht sehr nützlich. Sie sind viel besser dran, wenn Sie andere Mittel verwenden, um kontextsensitive Funktionen zu beschreiben.
Alex ten Brink
Aber Sie sprechen in den meisten Teilen Ihrer Antwort über Sprachen. In Bezug auf Grammatiken, ymmw. Es gibt Grammatikmodelle zwischen CFG und CSG, die natürliche Modellierungsanwendungen haben, z. B. Coupled- / Multi-CFG.
Raphael
1
Du hast recht, ich war schlampig mit der Unterscheidung zwischen Sprachen und Grammatiken, die ich sehe. Ich habe meine Antwort aktualisiert.
Alex ten Brink
10

L

AL(A)

Kurz gesagt, für kleinere Klassen benötigen Sie weniger Rechenleistung, um das Problem der Entscheidung zu lösen, ob ein Wort zur Sprache gehört.

Laut Wikipedia definierte Chomsky kontextsensitive Grammatiken (dh Typ 1), um die Syntax natürlicher Sprachen zu beschreiben. Dies ist ein bisschen anders als bei anderen Sprachklassen, die eingeführt wurden, um Familien von Zeichenfolgen zu beschreiben, die in der Mathematik verwendet wurden (z. B. die Syntax von arithmetischen Formeln) anstelle von natürlichen Sprachen (z. B. die Syntax eines grammatisch korrekten Satzes in Englisch). .

Janoma
quelle
2
"Kurz gesagt, für kleinere Klassen benötigen Sie weniger Rechenleistung, um das Problem der Entscheidung zu lösen, ob ein Wort zur Sprache gehört." Genau, aber wie trifft dies auf Typ 1 im Vergleich zu Typ 0 zu? Das ist genau die Frage!
Bitmaske
ccn
8

In kontextfreien Sprachen befindet sich der Automat zu jedem Zeitpunkt der Eingabe-Analyse in einem Zustand, der durch seinen Stapel definiert wird. Jede Produktion hat das gleiche Verhalten beim Verzehr der Eingabe, unabhängig davon, wo sie verwendet wird.

Dies führt zu der interessanten Eigenschaft, dass jede Produktion eine Subsprache derjenigen erzeugt, die von denjenigen erzeugt wird, die sich tiefer im Stapel befinden, und daher für jedes Paar A und B von Produktionen, die für eine bestimmte Eingabe erzeugt und verbraucht werden, drei mögliche Fälle vorliegen:

  • a: Die von A verbrauchte Eingabe ist vollständig in der von B verbrauchten Eingabe enthalten. oder
  • b: Die von A verbrauchte Eingabe enthält die von B verbrauchte Eingabe vollständig. oder
  • c: Die von A verbrauchte Eingabe ist vollständig von der von B verbrauchten Eingabe getrennt.

Dies impliziert, dass Folgendes niemals passiert:

  • d: Die von A verbrauchte Eingabe überlappt teilweise die von B verbrauchte Eingabe.

Im Gegensatz dazu hängt in kontextsensitiven Sprachen das Verhalten jeder Produktion davon ab, wo sie verwendet wird. Die in einer Produktion verbrauchte Eingabe ist also keine Untersprache derjenigen, die sich tiefer im Stapel befinden (in der Tat wird sie mit a verarbeitet) Stack würde nicht funktionieren). Und wir haben diese Möglichkeit, die passieren kann.

In der realen Welt ist ein Fall, in dem eine kontextsensitive Sprache Sinn macht, so etwas wie das Bezeichnen von <b> fettem Text </ b>, <i> kursivem Text </ i> und <u> unterstrichenem Text </ u> mit diese HTML-Tags und lassen Sie sie überlappen, wie "Dies ist ein <u> Text mit <i> gemischten </ u> überlappenden Tags </ i>." Beachten Sie, dass ein PDA, um das zu analysieren und festzustellen, ob alle Start-Tags mit den End-Tags übereinstimmen, nicht funktioniert, da er nicht kontextfrei ist, ein LBA jedoch problemlos.

Victor Stafusa
quelle
7

Verschlusseigenschaften

Von allen Sprachklassen der Chomsky-Hierarchie werden nur reguläre und kontextsensitive Sprachen in Ergänzung geschlossen . Daher ist dies eine Art einzigartiges Merkmal von kontextsensitiven Sprachen.

Im Gegensatz zu kontextfreien Sprachen werden CS auch unter intersection und shuffle product geschlossen .

Sebastian
quelle
6

Jede Sprache vom Typ 1 kann von einer Turing-Maschine erkannt werden, die nur den linearen Raum verwendet (sogenannte linear begrenzte Automaten).

Suresh
quelle
2
Ja, das ist die Definition. Aber wie hilft mir diese Einschränkung?
Bitmaske
3
Es hilft mir, weil es die Leistung von Algorithmen, die CSGs erkennen, auf E anstelle von EXP begrenzt. Ich weiß nicht, wie es Ihnen hilft :)
Suresh
5

Die Sprachen des Typs 1 können durch linear begrenzte Automaten bestimmt werden. Hierbei handelt es sich um nicht deterministische Turing-Maschinen, die möglicherweise nur einen Teil des Bands verwenden, dessen Größe linear zur Eingabegröße ist.

sepp2k
quelle
4

Die Chomsky-Hierarchie klassifiziert Grammatiken mehr als Sprachen. Es sollte jedoch nichts mit der Anzahl der Bänder zu tun haben, die ein Automat erkennen sollte, wie Sie für Typ 2 und 3 vorgeschlagen haben, auch wenn es eine Art Turing-Maschine gibt, die dies für Typ-1-Grammatiken tut.

Sie sollten auch beachten, dass die Sprachen der Typ-0-Grammatik nicht alle von einer Turing-Maschine erkannt werden, sondern nur von einer solchen Maschine aufgezählt werden können: Typ-0 bedeutet rekursiv aufzählbar, und Turing-Maschinen erkennen nur rekursive Sprachen.

jmad
quelle
4

Moderne Programmiersprachen verwenden ständig kontextsensitive Funktionen. Sie fallen in eine Untergruppe, die effizient entschieden werden kann.

Beispiele sind Namens- und Typanalyse und Typinferenz.

Raphael
quelle
3

Viele andere haben erwähnt, dass Typ-1-Sprachen solche sind, die von linear begrenzten Automaten erkannt werden können. Das Problem des Anhaltens ist für Automaten mit linearen Grenzen entscheidend, was wiederum bedeutet, dass viele andere Eigenschaften, die für von Drehmaschinen erkannte Sprachen rechnerisch nicht entscheidbar sind, für Sprachen des Typs 1 entscheidend sind.

Zugegebenermaßen beruht der Beweis, dass das Halteproblem für linear begrenzte Automaten entscheidbar ist, auf der Tatsache, dass sie mit einer begrenzten Anzahl von Bändern nur eine begrenzte Anzahl von Zuständen eingeben können. Wenn sie also nicht in so vielen Schritten anhalten, wissen Sie, dass sie es sind Looping und wird nie aufhören. Dieser Beweis gilt technisch für alle tatsächlichen Computer (die auch über endlichen Speicher verfügen), aber das ist für die Lösung des Halteproblems für die Programme, die auf ihnen ausgeführt werden, nicht von praktischem Nutzen.

Ben
quelle