Chomsky-Hierarchie – Wikipedia

Posted on by
before-content-x4

Hierarchie der Klassen formaler Grammatiken

 after-content-x4

In der formalen Sprachtheorie, Informatik und Linguistik ist die Chomsky-Hierarchie (gelegentlich als bezeichnet Chomsky-Schützenberger-Hierarchie)[1] ist eine Containment-Hierarchie von Klassen formaler Grammatiken.

Diese Hierarchie der Grammatiken wurde 1956 von Noam Chomsky beschrieben.[2] Es ist auch nach Marcel-Paul Schützenberger benannt, der eine entscheidende Rolle bei der Entwicklung der Theorie der formalen Sprachen spielte.

Formale Grammatiken[edit]

Eine formale Grammatik dieses Typs besteht aus einer endlichen Menge von Produktionsregeln (links → rechte Seite), wobei jede Seite aus einer endlichen Folge der folgenden Symbole besteht:

  • eine endliche Menge von Nichtterminale Symbole (zeigt an, dass einige Produktionsregeln noch angewendet werden können)
  • eine endliche Menge von Terminalsymbole (zeigt an, dass keine Produktionsregel angewendet werden kann)
  • ein Startsymbol (ein ausgezeichnetes nichtterminales Symbol)

Eine formale Grammatik liefert ein Axiomschema für (oder erzeugt) ein formelle SpracheDies ist eine (normalerweise unendliche) Menge von Symbolfolgen endlicher Länge, die durch Anwenden von Produktionsregeln auf eine andere Folge von Symbolen (die anfänglich nur das Startsymbol enthält) erstellt werden können. Eine Regel kann angewendet werden, indem das Auftreten der Symbole auf der linken Seite durch diejenigen ersetzt wird, die auf der rechten Seite angezeigt werden. Eine Folge von Regelanwendungen wird als a bezeichnet Ableitung. Eine solche Grammatik definiert die formale Sprache: Alle Wörter bestehen ausschließlich aus Endsymbolen, die durch Ableitung vom Startsymbol erreicht werden können.

Nichtterminale werden häufig durch Großbuchstaben, Terminals durch Kleinbuchstaben und das Startsymbol durch dargestellt S.. Zum Beispiel die Grammatik mit Terminals {a, b}}, nicht terminale {S, A, B.}}Produktionsregeln

S. → AB
S. → ε (wo ε ist die leere Zeichenfolge)
EIN → wie
B. → b

und Startsymbol S., definiert die Sprache aller Wörter der Form

after-content-x4
einnbn{ displaystyle a ^ {n} b ^ {n}}

(dh n Kopien von ein gefolgt von n Kopien von b).

Das Folgende ist eine einfachere Grammatik, die dieselbe Sprache definiert:

Terminals {a, b}}, Nichtterminale {S.}}, Startsymbol S., Produktionsregeln

S. → aSb
S. → ε

Als weiteres Beispiel wird eine Grammatik für eine Spielzeuguntermenge der englischen Sprache gegeben durch:

Terminals
{generieren, hassen, großartig, grün, Ideen, Linguisten}
Nichtterminale
{SENTENCE, NOUNPHRASE, VERBPHRASE, NOUN, VERB, ADJ}}
Produktionsregeln
SATZ → NOUNPHRASE VERBALPHRASE
NOUNPHRASE → ADJ NOUNPHRASE
NOUNPHRASE → SUBSTANTIV
VERBALPHRASE → VERB NOUNPHRASE
VERBALPHRASE → VERB
SUBSTANTIV → Ideen
SUBSTANTIV → Linguisten
VERB → generieren
VERB → Hass
ADJ → großartig
ADJ → Grün

und Startsymbol SATZ. Eine beispielhafte Ableitung ist

SATZ → NOUNPHRASE VERBPHRASE → ADJ NOUNPHRASE VERBPHRASE → ADJ NOUN VERBPHRASE → ADJ NOUN VERB NOUNPHRASE → ADJ NOUN VERB ADJ NOUNPHRASE → ADJ NOUN VERB ADJ ADJ NOUNPHRASE → ADJ NOUN VERB ADJ ADJ NOUN → großartig NOUN VERB ADJ ADJ NOUN → große Linguisten VERB ADJ ADJ NOUN → große Linguisten erzeugen ADJ ADJ NOUN → große Linguisten erzeugen große ADJ NOUN → Große Linguisten erzeugen großes Grün SUBSTANTIV → Großartige Linguisten bringen großartige grüne Ideen hervor.

Andere Sequenzen, die aus dieser Grammatik abgeleitet werden können, sind: “Ideen hassen große Linguisten“, und “Ideen erzeugen“. Während diese Sätze unsinnig sind, sind sie syntaktisch korrekt. Ein syntaktisch falscher Satz (z.”Ideen Ideen großer Hass“) kann nicht aus dieser Grammatik abgeleitet werden. Siehe” Farblose grüne Ideen schlafen wütend “für ein ähnliches Beispiel, das Chomsky 1957 gegeben hat; siehe Phrasenstrukturgrammatik und Phrasenstrukturregeln für natürlichere Sprachbeispiele und die Probleme der formalen Grammatik in diesem Bereich.

Die Hierarchie[edit]

Die Chomsky-Hierarchie

Stellen Sie Einschlüsse ein, die durch die Chomsky-Hierarchie beschrieben werden

In der folgenden Tabelle sind die vier Grammatiktypen von Chomsky, die von ihm erzeugte Sprachklasse, der Typ des Automaten, der sie erkennt, und die Form der Regeln zusammengefasst.

Beachten Sie, dass der Grammatiksatz, der rekursiven Sprachen entspricht, kein Mitglied dieser Hierarchie ist. Diese liegen ordnungsgemäß zwischen Typ 0 und Typ 1.

Jede reguläre Sprache ist kontextfrei, jede kontextfreie Sprache ist kontextsensitiv, jede kontextsensitive Sprache ist rekursiv und jede rekursive Sprache ist rekursiv aufzählbar. Dies sind alles richtige Einschlüsse, was bedeutet, dass es rekursiv aufzählbare Sprachen gibt, die nicht kontextsensitiv sind, kontextsensitive Sprachen, die nicht kontextfrei sind, und kontextfreie Sprachen, die nicht regulär sind.[4]

Typ-0-Grammatiken[edit]

Typ-0-Grammatiken umfassen alle formalen Grammatiken. Sie erzeugen genau alle Sprachen, die von einer Turing-Maschine erkannt werden können. Diese Sprachen werden auch als bezeichnet rekursiv aufzählbar oder Turing-erkennbar Sprachen.[5] Beachten Sie, dass sich dies von den rekursiven Sprachen unterscheidet, die es sein können beschlossen von einer immer stoppenden Turingmaschine.

Typ-1-Grammatiken[edit]

Typ-1-Grammatiken erzeugen kontextsensitive Sprachen. Diese Grammatiken haben Regeln der Form

αEINβ→αγβ{ displaystyle alpha A beta rightarrow alpha gamma beta}

mit

EIN{ displaystyle A}

ein Nichtterminal und

α{ displaystyle alpha}

,

β{ displaystyle beta}

und

γ{ displaystyle gamma}

Zeichenfolgen von Terminals und / oder Nicht-Terminals. Die Saiten

α{ displaystyle alpha}

und

β{ displaystyle beta}

kann leer sein, aber

γ{ displaystyle gamma}

muss nicht leer sein. Die Regel

S.→ϵ{ displaystyle S rightarrow epsilon}

ist erlaubt wenn

S.{ displaystyle S}

erscheint nicht auf der rechten Seite einer Regel. Die von diesen Grammatiken beschriebenen Sprachen sind genau alle Sprachen, die von einem linear begrenzten Automaten erkannt werden können (einer nichtdeterministischen Turing-Maschine, deren Band durch ein konstantes mal die Länge der Eingabe begrenzt ist).

Typ-2-Grammatiken[edit]

Typ-2-Grammatiken erzeugen die kontextfreien Sprachen. Diese werden durch Regeln des Formulars definiert

EIN→α{ displaystyle A rightarrow alpha}

mit

EIN{ displaystyle A}

ein Nichtterminal sein und

α{ displaystyle alpha}

eine Folge von Terminals und / oder Nicht-Terminals sein. Diese Sprachen sind genau alle Sprachen, die von einem nicht deterministischen Pushdown-Automaten erkannt werden können. Kontextfreie Sprachen – oder vielmehr ihre Teilmenge der deterministischen kontextfreien Sprache – sind die theoretische Grundlage für die Phrasenstruktur der meisten Programmiersprachen, obwohl ihre Syntax aufgrund von Deklarationen und Umfang auch eine kontextsensitive Namensauflösung umfasst. Oft wird eine Teilmenge von Grammatiken verwendet, um das Parsen zu vereinfachen, beispielsweise durch einen LL-Parser.

Typ-3-Grammatiken[edit]

Typ-3-Grammatiken erzeugen die regulären Sprachen. Eine solche Grammatik beschränkt ihre Regeln auf ein einzelnes Nichtterminal auf der linken Seite und eine rechte Seite, die aus einem einzelnen Terminal besteht, möglicherweise gefolgt von einem einzelnen Nichtterminal (rechts regulär). Alternativ kann die rechte Seite der Grammatik aus einem einzelnen Terminal bestehen, dem möglicherweise ein einzelnes Nichtterminal (links regulär) vorangestellt ist. Diese erzeugen die gleichen Sprachen. Wenn jedoch links-reguläre Regeln und rechts-reguläre Regeln kombiniert werden, muss die Sprache nicht mehr regulär sein. Die Regel

S.→ϵ{ displaystyle S rightarrow epsilon}

ist auch hier erlaubt wenn

S.{ displaystyle S}

erscheint nicht auf der rechten Seite einer Regel. Diese Sprachen sind genau alle Sprachen, die von einem endlichen Automaten bestimmt werden können. Zusätzlich kann diese Familie formaler Sprachen durch reguläre Ausdrücke erhalten werden. Normale Sprachen werden häufig verwendet, um Suchmuster und die lexikalische Struktur von Programmiersprachen zu definieren.

Verweise[edit]

  1. ^ Silberztein, Max (2013). “NooJ Computational Devices”. Formalisierung natürlicher Sprachen mit NooJ. S. 1–13. ISBN 978-1-4438-4733-9.
  2. ^ Chomsky, Noam (1956). “Drei Modelle zur Beschreibung der Sprache” (PDF). IRE-Transaktionen zur Informationstheorie (2): 113–124. doi:10.1109 / TIT.1956.1056813.
  3. ^ Geuvers, H.; Rot, J. (2016). “Anwendungen, Chomsky-Hierarchie und Zusammenfassung” (PDF). Reguläre Sprachen.
  4. ^ Chomsky, Noam (1963). “Kapitel 12: Formale Eigenschaften von Grammatiken”. In Luce, R. Duncan; Bush, Robert R.; Galanter, Eugene (Hrsg.). Handbuch der mathematischen Psychologie. II. John Wiley and Sons, Inc., S. 323–418.
  5. ^ Sipser, Michael (1997). Einführung in die Theorie der Berechnung (1. Aufl.). Lernen einbinden. p. 130. ISBN 0-534-94728-X. Die kirchliche These


after-content-x4