Das Kefk Network Wiki befindet sich im Testbetrieb.

Chomsky-Hierarchie

Aus Kefk.

Wechseln zu: Navigation, Suche

Chomsky-Hierarchie, gelegentl. Chomsky–Schützenberger-Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen. Sie wurde 1956 erstmals von Noam Chomsky beschrieben. Die vier von Chomsky beschriebenen Grammatiktypen entstehen dabei ausgehend von einer nicht eingeschränkten Grundgrammatik (der Typ-0-Grammatik) dergestalt, dass zunehmend Einschränkungen bezüglich der für den Typ erlaubten Produktionsregeln gemacht werden.

Entsprechend dem Typ einer Grammatik, die mindestens erforderlich ist, um eine bestimmte formale Sprache zu erzeugen, werden auch formale Sprachen in dieselben Kategorien von Typ 0 bis Typ 3 eingeteilt.

Sei im Folgenden die formale Grammatik G = \left( N, \Sigma, P, S \right) angenommen. N stellt die Menge der Nichtterminalsymbole, Σ die Menge der Terminalsymbole, P die Menge von Produktionsregeln und S das Startsymbol dar (Einzelheiten siehe unter formale Grammatik).

Inhaltsverzeichnis

Übersicht

Die folgende Tabelle fasst die vier Grammatiktypen, die Form ihrer Regeln, die Sprachen, die sie erzeugen und die Automatentypen, die sie erkennen, zusammen. Zudem wird die Abgeschlossenheit der erzeugten Sprachen bezüglich einiger Operationen angegeben.

Grammatik Regeln Sprachen Automaten Abgeschlossenheit
Typ-0 \alpha \rightarrow \beta
\alpha, \beta \in V^*, \alpha \neq \epsilon 		rekursiv aufzählbar Turing-Maschine KSV*
Typ-1 \alpha A \beta \rightarrow \alpha \gamma \beta
A \in N, \alpha, \beta, \gamma \in V^*, \gamma \neq \epsilon 		kontextsensitiv linear platzbeschränkte nichtdeterministische Turing-Maschine CKSV*
Typ-2 A \rightarrow \gamma
A \in N, \gamma \in V^* 		kontextfrei nichtdeterministischer Kellerautomat KV*
Typ-3 A \rightarrow aB (rechtsregulär) oder
A \rightarrow Ba (linksregulär)
A \rightarrow a
A,B \in N, a \in \Sigma 		regulär (deterministischer) Endlicher Automat CKSV*

Mengensymbole

  • Σ: Menge der Terminale
  • N: Menge der Nichtterminale
  • V=\Sigma \cup N: Menge der Variablen

Abgeschlossenheit

Die Hierarchie

Typ-0-Grammatik (allgemeine Chomsky-Grammatik oder Phrasenstrukturgrammatik)

Typ-0-Grammatiken werden auch unbeschränkte Grammatiken genannt. Es handelt sich dabei um alle definierbaren Grammatiken.

Man schreibt G \in \mbox{Typ}_0.

Jede Typ-0-Grammatik erzeugt eine Sprache, die von einer Turing-Maschine akzeptiert werden kann und umgekehrt existiert für jede Sprache, die von einer Turingmaschine akzeptiert werden kann, eine Typ-0-Grammatik, die diese Sprache erzeugt. Diese Sprachen sind auch bekannt als die rekursiv aufzählbaren Sprachen (oft auch semi-entscheidbare Sprachen genannt). Man beachte, dass sich diese Menge von Sprachen von der Menge der rekursiven Sprachen (oft auch entscheidbare Sprachen genannt) unterscheidet, welche durch Turing-Maschinen erkannt (oder auch akzeptiert) werden können, d. h. die zugehörige Turingmaschine hält bei jedem Wort, das in der Sprache liegt, und liefert das Ergebnis 1. Es kann jedoch vorkommen, dass die Turingmaschine auf Worten, die nicht in der Sprache liegen, niemals anhält.

Typ-1-Grammatik (kontextsensitive bzw. monotone Grammatik)

Typ-1-Grammatiken werden auch kontextsensitive Grammatiken genannt. Es handelt sich dabei um Typ-0-Grammatiken mit \forall (w_1 \rightarrow w_2) \in P : \left| w_1 \right| \le \left| w_2 \right|.

Man schreibt G \in \mbox{Typ}_1.

Sie erzeugen genau die kontextsensitiven Sprachen, d.h. jede Typ-1-Grammatik erzeugt eine kontextsensitive Sprache und zu jeder kontextsensitiven Sprache existiert eine Typ-1-Grammatik, die diese erzeugt.

Typ-1-Grammatiken besitzen nur Regeln der Form \alpha A \beta \rightarrow \alpha \gamma \beta, wobei A ein Nichtterminal und αγβ Wörter bestehend aus Terminalen (Σ) und Nichtterminalen (N) sind. Die Wörter α und β können leer sein, aber γ muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten. Diese Eigenschaft wird oft Längenbeschränktheit genannt.

Die einzige Ausnahme ist, dass die Grammatik die Regel S \rightarrow \varepsilon ausgehend vom Startsymbol S enthalten darf. Diese Regel wird eventuell benötigt, um das leere Wort \varepsilon ableiten zu können. Die Regel S \rightarrow \varepsilon darf aber nur dann verwendet werden, wenn das Startsymbol S auf keiner rechten Seite der Produktionsregeln auftritt.

Die kontextsensitiven Sprachen sind genau die Sprachen, die von einer nichtdeterministischen, linear beschränkten Turingmaschine erkannt werden können; d.h. von einer nichtdeterministischen Turing-Maschine, deren Band linear durch die Länge der Eingabe beschränkt ist (d.h. es gibt eine konstante Zahl a so dass das Band der Turing-Maschine höchstens a \cdot x Felder besitzt, wobei x die Länge des Eingabewortes ist).

Im Unterschied zu kontextfreien Grammatiken kann die Anzahl der Symbole auf der linken Seite einer kontextsensitiven Grammatik > 1 sein.

Typ-2-Grammatik (kontextfreie Grammatik)

Typ-2-Grammatiken werden auch kontextfreie Grammatiken genannt. Es handelt sich dabei um Typ-1-Grammatiken mit \forall (w_1 \rightarrow w_2) \in P : ( w_1 \in N) \and \left(w_2 \in (N \cup \Sigma)^\star\right).

Man schreibt G \in \mbox{Typ}_2.

Sie erzeugen genau die kontextfreien Sprachen, d. h. jede Typ-2-Grammatik erzeugt eine kontextfreie Sprache und zu jeder kontextfreien Sprache existiert eine Typ-2-Grammatik, die diese erzeugt.

Typ-2-Grammatiken besitzen nur Regeln der Form A \rightarrow \gamma, wobei A ein Nichtterminal und γ ein Wort bestehend aus Terminalen und Nichtterminalen ist. (Um das leere Wort \varepsilon zu erzeugen, darf hier für γ auch \varepsilon verwendet werden.)

Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen Kellerautomaten (NPDA) erkannt werden können. Eine Teilmenge dieser Sprachen bildet die theoretische Basis für die Syntax der meisten Programmiersprachen.

Siehe auch hier: Backus-Naur-Form

Typ-3-Grammatik (rechtslineare bzw. linkslineare Grammatik)

Typ-3-Grammatiken werden auch reguläre Grammatiken genannt. Es handelt sich dabei um Typ-2-Grammatiken mit \forall (w_1 \rightarrow w_2) \in P : w_1 \in N und w_2 \in \Sigma \cup \Sigma \cdot N \cup \{ \varepsilon \}.

Man schreibt G \in \mbox{Typ}_3.

Sie erzeugen genau die regulären Sprachen, das heißt, jede Typ-3-Grammatik erzeugt eine reguläre Sprache und zu jeder regulären Sprache existiert eine Typ-3-Grammatik, die diese erzeugt.

Typ-3-Grammatiken besitzen entweder nur Regeln, die auf der linken Seite aus einem Nichtterminal und auf der rechten Seite aus einem Terminal, eventuell gefolgt von einem Nichtterminal bestehen (rechtslineare Grammatik) oder nur Regeln, die auf der linken Seite aus einem Nichtterminal und auf der rechten Seite aus einem Terminal, eventuell mit vorangestelltem Nichtterminal bestehen (linkslineare Grammatik) …

Zu jeder linkslinearen Grammatik gibt es auch eine rechtslineare Grammatik (und umgekehrt), welche die selbe Sprache erzeugt.

Reguläre Sprachen können alternativ auch durch reguläre Ausdrücke beschrieben werden und die regulären Sprachen sind genau die Sprachen, die von endlichen Automaten erkannt werden können. Sie werden gewöhnlich genutzt, um Suchmuster oder die lexikalische Struktur von Programmiersprachen zu definieren.

Chomsky-Hierarchie für formale Sprachen

Es sei Σ ein Alphabet. Eine formale Sprache L ist vom Typ i \in \{ 0, ..., 3 \}, falls es eine Grammatik G \in \mbox{Typ}_i mit L = L \left( G \right) gibt. Man schreibt dann L \in \mathcal{L}_i.

Jede reguläre Sprache ist kontextfrei, jede kontextfreie Sprache ist kontextsensitiv und jede kontextsensitive Sprache ist rekursiv aufzählbar.

Dabei handelt es sich um echte Teilmengenbeziehungen, d. h. es gibt rekursive aufzählbare Sprachen, die nicht kontextsensitiv sind, kontextsensitive Sprachen, die nicht kontextfrei sind und kontextfreie Sprachen, die nicht regulär sind.

Formal ausgedrückt bedeutet dies für die Klassen der durch die obigen Grammatiken erzeugten Sprachen:

\mathcal{L}_3 \subset \mathcal{L}_2 \subset \mathcal{L}_1 \subset \mathcal{L}_0

wobei gelegentlich auch folgende Symbole verwendet werden:

REG \subset CF \subset CS \subset RE

Beispiele für Sprachen in den jeweiligen Differenzmengen sind:

  • Das Halteproblem ist vom Typ 0, aber nicht vom Typ 1
  • L_1 = \left\{a^n b^n c^n | n \ge 1\right\} ist vom Typ 1, aber nicht vom Typ 2
  • L_2 = \left\{a^n b^n | n \ge 1\right\} ist vom Typ 2, aber nicht vom Typ 3

Natürliche Sprachen

Obwohl Chomsky seine Forschungen mit dem Ziel verfolgte, eine mathematische Beschreibung der natürlichen Sprachen zu finden, ist bis heute der Nachweis einer (formalen) Grammatik nur für die wenigsten Sprachen gelungen, die meisten davon konstruierte Plansprachen. Das Problem besteht vor allem in der Mehrdeutigkeit menschlicher Kommunikation mit ihren verschiedenen Bedeutungsebenen. So kann der Satz "Er macht einen Haufen Mist." im wörtlichen als auch im übertragenen Sinne interpretiert werden. Die korrekte Bedeutung ergibt sich aus dem erweiterten Kontext, in dem dieser Satz steht oder kann sogar unaufgelöst bleiben. Selbst um die Mehrdeutigkeit überhaupt erst erkennen zu können, benötigt man einen kulturellen Hintergrund, der ebenfalls nicht mathematisch darstellbar ist. Die heutigen Übersetzungssysteme umgehen diese Formalisierung und nutzen Datenbanken mit Redewendungen, die den jeweiligen Kontext mitliefern. Die Übersetzung bleibt mechanisch. Die Bedeutung muss der Leser selbst dem Text entlocken. Wenn in einem übersetzten Text nur die Vokabeln stimmen, hat der menschliche Leser in der Regel keine Schwierigkeiten bei der inhaltlichen Erfassung; somit ist eine praktikable automatische Übersetzung ganz ohne Expertensystem möglich geworden.

Literatur

  • Noam Chomsky: Three models for the description of language. In: IRE Transactions on Information Theory 2 (1956), S. 113–124
  • Noam Chomsky: On certain formal properties of grammars. In: Information and Control 1 (1959), S. 91–112
  • Noam Chomsky, Marcel P. Schützenberger: The algebraic theory of context free languages, Computer Programming and Formal Languages (P. Braffort and D. Hirschberg ed.), North Holland, Amsterdam, 1963, 118-161.
  • Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit. B. G. Teubner, Stuttgart 1992, ISBN 3-519-02937-5
Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Chomsky-Hierarchie, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://kefk.org/wiki/Chomsky-Hierarchie“
Persönliche Werkzeuge