Formale Sprachtheorie und Automaten

Die Theorie der formalen Sprachen und der abstrakten Maschinen, die diese erkennen, liefert das Vokabular zur Beschreibung, wie komplex ein sprachliches Muster ist und welche Algorithmen es verarbeiten können.

Definition

Die Theorie der formalen Sprachen untersucht Mengen von Zeichenketten, die durch Grammatiken definiert sind, und die Automatentheorie untersucht die abstrakten Maschinen, die die Zugehörigkeit zu diesen Mengen entscheiden.

Scope

Umfasst die Chomsky-Hierarchie (reguläre, kontextfreie, kontextsensitive, rekursiv aufzählbare Sprachen), die entsprechenden Grammatiken und die erkennenden Automaten – endliche Automaten, Kellerautomaten und Turingmaschinen. Es werden Abschluss- und Entscheidbarkeitseigenschaften behandelt, die für die Sprachverarbeitung relevant sind, sowie die Frage, wo die natürliche Sprache in der Hierarchie einzuordnen ist. Pumping-Lemmata und vollständige Komplexitätsbeweise werden eher als Hintergrund denn als primärer Inhalt behandelt.

Core questions

• Welcher Automat entspricht jeder Ebene der Chomsky-Hierarchie?
• Wo ist die natürliche Sprache in der Hierarchie einzuordnen, und warum wird argumentiert, dass sie die kontextfreie Mächtigkeit übersteigt?
• Was bedeutet es, wenn eine Sprachklasse unter einer Operation abgeschlossen ist, und warum ist das für die Entwicklung wichtig?

Key concepts

• reguläre Sprache
• kontextfreie Grammatik
• kontextsensitive Grammatik
• endlicher Automat
• Kellerautomat
• Turingmaschine
• Abschlusseigenschaften
• milde Kontextsensitivität

Key theories

Chomsky-Hierarchie

Vier geschachtelte Klassen formaler Sprachen, die jeweils durch einen eingeschränkten Grammatiktyp erzeugt und von einem entsprechenden Automaten erkannt werden, wodurch sprachliche Konstruktionen nach der erforderlichen Rechenleistung geordnet werden.

Grammatik-Automaten-Korrespondenz

Jede Grammatikklasse ist nachweislich äquivalent zu einer Maschinenklasse – reguläre Grammatiken zu endlichen Automaten, kontextfreie Grammatiken zu Kellerautomaten – was generative Beschreibungen mit Erkennungsalgorithmen verknüpft.

History

Chomskys Arbeit von 1956 führte die Hierarchie als Teil eines Arguments ein, dass endliche Zustandsmodelle für die natürliche Sprache unzureichend seien. Die folgenden Jahrzehnte formalisierten die Automatenkorrespondenzen, und Computerlinguisten zeigten später, dass die natürliche Sprache höchstens eine „mild kontextsensitive“ Mächtigkeit erfordert, was Grammatikformalismen jenseits der Kontextfreiheit motivierte.

Debates

Ist natürliche Sprache kontextfrei?

Kreuzweise Abhängigkeiten in Sprachen wie dem Schweizerdeutschen wurden verwendet, um zu argumentieren, dass die natürliche Sprache die kontextfreie Mächtigkeit übersteigt, was zum Begriff der milden Kontextsensitivität als dem richtigen Grad an Ausdrucksfähigkeit führte.

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

Was ist der Unterschied zwischen einer regulären und einer kontextfreien Sprache?

Reguläre Sprachen können mit endlichem Speicher von einem endlichen Automaten erkannt werden; kontextfreie Sprachen können einen Stapel (einen Kellerautomaten) erfordern, um geschachtelte Strukturen, wie z. B. Klammerpaare oder eingebettete Nebensätze, zu verfolgen.