Die Chomsky-Hierarchie
Benannt nach dem Linguisten Noam Chomsky
Grundlegende Klassifizierung
| Typ | Art der Grammatik | Typ der Sprache | akzeptierende Maschine |
|---|---|---|---|
| 0 | unbeschränkt | aufzählbare Sprachen | Turingmaschine |
| 1 | kontextsensitiv | kontextsensitive Sprachen | linear beschränkte Turingmaschine |
| 2 | kontextfrei | kontextfreie Sprachen | Kellerautomat |
| 3 | rechtslinear | reguläre Sprachen | endlicher Automat |
Quelle: Brichzin, Peter; Freiberger, Ulrich; Reinhold, Klaus; Wiedemann, Albert. INFORMATIK Oberstufe 2. Cornelsen, München. 2016¹ S. 52
Abhängigkeiten der Typen
Jeder Typ (außer 0), ist jeweils im nächsthöheren enthalten, z.B. ist jede reguläre Sprache auch eine kontextfreie usw. (siehe Abbildung).
Quelle: wikipedia.org
Genauere Erklärung von Typ 2 und 3
Typ 2
Kontextfreie Grammatik (aus Unterricht bekannt):
- 4-Tupel aus G=(V, ∑, P, S)
- V: endliche Menge der Nichtterminalsymbole (Variablen)
- ∑: endliche Menge der Terminalsymbole
- P: endliche Menge der Produktionsregeln (mit jeweils genau einem Nichtterminal der Sprache auf der linken Seite)
- S: Startsymbol (S ∈V)
Eine kontextfreie Grammatik erzeugt eine kontextfreie Sprache und zu jeder kontextfreien Sprache gibt es eine kontextfreie Grammatik.
Chomsky-Normalform (CNF):
- jede kontextfreie Grammatik kann in die CNF überführt werden
- schränkt rechte Seite der Produktionsregeln ein. In jeder Regel ist nur eine der folgenden Formen möglich:
- ein einziges Terminalsymbol
- zwei Nichtterminal-Symbole
- wenn links S ist, das leere Wort
Kontextfreie Sprachen:
- formale Sprache, die durch kontextfreie Grammatik beschrieben werden kann
- ob Eingabe den Regeln entspricht, kann durch Parser geprüft werden
- Akzeptierung durch einen Kellerautomaten (nichtdeterministisch und deterministisch möglich)
Entscheidungsprobleme:
- entscheidbare (rekursiv ableitbare) Probleme:
- Wortproblem (gehört ein Wort aus einem festgelegten Alphabet zu einer kontextfreien Sprache?)
- Leerheitsproblem (Ist die Sprache eine leere Menge?)
- Endlichkeitsproblem (Ist die Menge der, in der Sprach enthaltenen, Wörter endlich?)
- nicht entscheidbar: Äquivalenzproblem (gilt für 2 Sprachen, mit demselben Alphabet L1=L2?)
Kellerautomat
- Keller ist andere Bezeichnung für Stack
- Fehlerüberprüfung über Stack, anstatt Trap State
Beispiel für kontextfreie Grammatik und dazugehöriger (deterministischer) Kellerautomat
Überprüfung, ob eine Zeichenkette die gleiche Anzahl an geschlossenen und offenen geschweiften Klammern enthält
Video: Erklärung des Kellerautomaten
Download der jar (enthält auch den source code)
Typ 3
rechtsreguläre/rechtslineare Grammatik:
- aufgebaut wie kontextfreie Grammatik
- Einschränkungen in Produktionsregeln, rechte Seite darf nur sein:
- das leere Wort
- ein/mehrere Terminalsymbole
- ein/mehrere Terminalsymbole und ein einziges Nichtterminal-Symbol
- bei jeder Anwendung einer Regel, Erweiterung der Zeichenkette um eine Stelle nach rechts (=>rechtslinear)
Reguläre Sprachen:
- formale Sprache, die:
- durch eine reguläre Grammatik beschrieben werden kann
- von einem endlichen Automaten akzeptiert wird
- durch einen regulären Ausdruck dargestellt werden kann
Beispiel:
Automat zu folgender RegEx-Epression: (.+\.)*(google)(\.com) => beschreibt die Domain google.com, sowie alle Subdomains. (Alphabet in Grafik durch RegEx Ausdrücke verkürzt dargestellt)
Erklärung zu RegEx: https://docs.pi-hole.net/ftldns/regex/tutorial/
