Chomsky hierarchie
Kurzreferat zu Sprachen und Gramatiken in Bezug auf Unterteilung in Typen
1. Grammatik und Sprache
- Notation
- Definition Grammatik
- Bestandteildefinition
- Definition Formale Sprache
- Definition Aufzählbare Sprachen
- Definition Entscheibare Sprachen
- Definition Reguläre Sprachen
2. Typ-0-Sprachen
- Typ-0-Grammatik
- Beispiel
- Turingmaschine
3. Typ-1-Sprachen
- kontextsensitive Grammatik
- Beispiel
- linear beschränkter Automat
4. Typ-2-Sprachen
- kontextfreie Grammatik
- Beispiel
- Kellerautomaten
5. Typ-3-Sprachen
- Reguläre Grammatik
- Beispiel
- endlicher Automat
1.
Grammatik und Sprache
1.1 Notation:
Nichtterminalsymbole werden in Backus-Naur-Form, in spitzen Klammern < >, gesetzt.
Der Pfeil ® einer Produktionsregel wird durch das Zeichen ::= dargestellt.
Alternativen werden durch einen senkrechten Strich ½ getrennt.
Geschwungene Klammern {} bedeuten Wiederholungen und eckige Klammern [] umschließen optionale Teile.
1.
2 Definition Grammatik:
Eine Grammatik G=(T,N,P,S) ist ein Viertupel mit:
. T endliche Menge der terminalen Symbole
. N endliche Menge der nichtterminalen Symbole, T Ç N = Ø
. P Produktionssystem mit endlich vielen Produktionsregeln
. S 0 N, Startsymbol
1.3 Bestandteildefinition:
Terminale T: Das Alphabet der Sprache. Terminalsymbole sind Zeichen oder Wörter, die nicht mehr weiter zerlegt werden können und mit denen jeder Satz einer Sprache formuliert wird.
Tdeutsch = {a, ...
z, A, ...Z, der, die , das, Professor, Studentin, ...
}
T*: Menge aller Wörter, die durch die Hintereinanderreihung endlich vieler Terminalsymbole einschließlich des leeren Wortes e, erzeugt werden können
Nichtterminale N: Hilfssymbole, mit deren Hilfe die Grammatikregeln formuliert werden können. Jedes nichtterminale Symbol entspricht einer Variablen und läßt sich in eine Folge anderer nichtterminaler und terminaler Symbole umschreiben.
Ndeutsch = {<Satz>, <Subjekt>, <Prädikat>, <Objekt>, <Artikel>,
<Substantiv>, <Verb>, <Attribut>, ...}
Äquivalent zu T* wird N* definiert.
Produktionen P: enthält Regeln zur Konstruktion von Zeichenketten der Sprache und legen fest, wie ein nichtterminales Symbol weiter ersetzt werden kann. Sie werden meistens in der Notation u ® v angegeben.
Es gilt: u,v 0 (T È N)*
Damit eine solche Regel anwendbar ist, muß u mindestens ein Nichtterminalsymbol enthalten.
<Satz> ® <Subjekt> <Prädikat> <Objekt>.
Das bedeutet, daß ein Satz aus einem Subjekt, einem Prädikat, einem Objekt und einem Punkt an dessen Ende besteht.
Startsymbol S: Ein Startsymbol S ist ein ausgezeichnetes nichtterminales Symbol mit dem jede Anwendung von Produktionsregeln beginnt.
Beispielsweise ist für die deutsche Sprache das nichtterminale Symbol "Satz" ein Startsymbol.
1.4 Definition Formale Sprache (allgem. Sprache)
Die von der Grammatik G erzeugte formale Sprache L(G) wird definiert durch die Menge aller Wörter w, die nur aus Terminalsymbolen bestehen und die alle aus dem Startsymbol S ableitbar sind. (Übersichten zum Gesamtverständnis der Sprachen, Automaten, Grammatiken und ihrer Zusammenhänge finden sie in den Anlagen)
1.5 Definition Aufzählbare Sprachen
Eine Sprache L(G) heißt aufzählbar, wenn es einen Algorithmus gibt, der alle Wörter w dieser Sprache nacheinander erzeugen kann.
Dazu gehören:
- Typ-0-Sprachen
- Sprachen die von Turingmaschinen mit eingeschränktem Eingabeband akzeptiert werden
1.6 Definition Entscheidbar Sprachen
Eine Sprache L(G) über einer Mnege von Terminalsymbolen T, L(G) Í T* , heißt entscheidbar, wenn es eien Algorithmus gibt, der nach endlich vielen Schritten feststellt, ob für jedes w Í T* gilt, daß entweder w Î L(G) oder w Ï L(G) zutrifft.
- bilden echte Teilmengen der aufzählbaren Sprachen
- sind echte Obermenge der kontextsensitiven Sprachen
- werden durch Kellerautokaten erkannt. Dies sind endliche Automaten, die um eine Keller erweitert werden, um bereits erkannte Zeichen zu speichern
2. Typ-0-Sprachen
Dies sind Sprachen mit einer Typ-0-Grammatik.
2.
1 Typ-0-Grammatik
Dies ist eine Grammatik ohne Einschränkungen.
"u ® v aus P gilt: u Î (T È N)+ = (T È N)* {e}, v Î (T È N)*
Die beiden damit verknüpften Forderungen sind die, daß auf der linken Seite mindestens ein Nichtterminalsymbol stehen muß und u nicht das leere Wort e ist.
2.2 Beispiel
Die folgende Grammatik erzeugt die Sprache L(G)={ai ½ mit i als positive Zweierpotenz}
G=(T, N, P, S)
G=({S, A, B, C, D, E},{a}, P, S)
P={S ® ACaB, aD ® Da, Ca ® aaC, AD ® AC, CB ® DB, aE ® Ea, CB ® E, AE ® e}
Bsp.:
S ® ACaB ® AaaCB ® AaaE ® aa(e) = aa
2.3 Turingmaschine
Eine Turingmaschine akzeptiert Sprachen die nach einer Typ-0-Grammatik gebildet werden.
Eine Turingmaschine ist ein 7-Tupel T = (X,B,Z,d,b,z0,ZE), wobei gilt:
- X ist eine nichtleere, endliche Menge, das Eingabealphabet,
- B Ê X ist eine nichtleere, endliche Menge, das Bandalphabet,
- Z ist eine nichtleere, endliche Menge, die Zustandsmenge,
- d: (ZZE) x B ® B x {L,N,R} x Z ist eine Funktion, die Überführungsfunktion, welche jedem Paar(Zustand, gelesenen Zeichen) ein Tripel (zu schreibendes Zeichen, Kopfbewegung, Folgezustand) zuordnet,
- b Î BX ist das Leerzeichen oder Blank,
- z0 Î Z ist der Anfangszustand,
- ZE Í Z ist die Endzustandsmenge
3. Typ-1-Sprachen
Dies sind Sprachen mit einer Typ-1-Grammatik.
3.1 kontextsensitive Grammatik
Die Einschränkung besteht darin, daß auf der linken Seite der Produktion ein nichtterminales Symbol existieren muß, das nur unter Beibehaltung eines Kontextes, sofern ein solcher vorhanden ist, ersetzt werden darf:
"x ® y aus P, $ A Î N und w1, w2, v Î (T È N)* mit v ¹ e, so daß aus x = w1Aw2 folgt y=w1vw2
Dies bedeutet, daß A nur im Kontext w1...
w2 durch v ersetzt werden darf.
3.2 Beispiel
Hierbei entsteht aus der nun folgenden Gramatik die Sprache L(G)={si,ti,ui}mit i Î N
G = {T, N, P, S)
T = {S, A, B}
N = {s, t, u}
S = S
P = {S ® sAtu½stu, A ® sAtB½stB, Bt ® tB, Bu ® uu}
Bsp.:
S ® stu
S ® sAtu ® sstBtu ® ssttBu ® ssttuu
S ® sAtu ® ssAtBtu ® sAttBu ® ssAttuu ® ssstBttuu ® sssttBtuu ® ssstttuuu
3.3 Linear beschränkter Automat
Linear beschränkte Automaten nutzen Typ-1-Sprachen.
Definition: Eine Struktur B = (X, Y, Z, h, z0, F, [, ] ) heißt linear beschränkter Automat,
wenn:
- (X, Y, Z, h, z0, F) ein (nichtdeterministischer) Turing-Automat (ohne Blank),
- [ , ] Î Y ( X ÈZ ) (linke bzw.
rechte Randmarke) und
- aus (y´, z´, o) h Î (y, z) folgt y´ = [ bzw. ] genau dann, wenn y = [ bzw. ]und aus y = [ bzw ] folgt o ¹ l bzw. r . (Die Randmarken dürfen wedergeschrieben, verändert, noch überschritten werden.
4.
Typ-2-Sprachen
Dies sind Sprachen mit einer Typ-2-Grammatik.
4.1 kontextfreie Grammatik
Für die Regeln aus P wird jetzt noch restriktiver gefordert, daß auf der linken Seite genau ein Nichtterminal stehen muß:
"u ® v aus P gilt: u Î N und v Î (T È N)* mit v ¹ e
Mit kontextfreien Grammatiken kann z.B. die Syntax von Programmiersprachen, wie Turbo Pascal (mein Liebling), festgelegt werden.
Zulässig: A ® aBa, A ® abBCa
Verboten: aBc ® abBCc (diese wäre kontextsensitiv!)
4.
2 Beispiel
G = (T, N, P, S)
T = {S, A, T, R}
N = {(, ), +, -, *, /, a, b, c, d, , e}
S = S
P = { S ® A, A ® T½+T½-T½A+T½A-T, T ® P½T*P½T/P, P ® (A) ½a½b½c½d½e}
Bsp.:
S ® A ® A+T ® T+P ® P+a ® b+a
4.3 Kellerautomat
Kellerautomaten nutzen kontextfreie Sprachen.
Definition: Eine Struktur K = ( X, Y, Z, h, z0, S, F ) heißt (endlicher) Kellerautomat, wenn
- X (Eingabealphabet), Y (Kelleralphabet), Z (Zustandsmenge) nichtleere endliche Mengen,
- z0 Î Z (Anfangszustand), S Î Y (Startsymbol), F Í Z (Endzustandsmenge),
- h eine Funktion aus ( X È {e} ) x Z x Y in die Menge aller endlichen Teilmengen von Z x Y*.
5. Typ-3-Sprachen
Dies sind Sprachen, die durch Typ-3-Grammatiken definiert werden.
5.1 Reguläre Grammatik
Dies ist eine kontextfreie Grammatik, die dadurch eingeschränkt wird, daß auf der rechten Seite jeder Regel neben terminalen Symbolen höchstens ein nichtterminales Symbol steht. Tritt auf der rechten Seite ein Nichtterminal auf, so muß es für alle Produktionsregeln einheitlich nur ganz rechts oder nur ganz links stehen:
"u ® v aus P gilt: u Î N und v Î T* o N oder v Î T* (v ¹ e) (rechtslinear)
"u ® v aus P gilt: u Î N und v Î N o T* oder v Î T* (v ¹ e) (linkslinear)
Dabei bedeutet o das Konkatenationszeichen. Das bislang verwendete Verbundzeichen È kann nicht eingesetzt werden, da es hier auf die genaue Reihenfolge ankommt und der Verbund von Mengen kommutativ ist.
Zulässig: A ® aaB, B ® b
Verboten: A ® aBa, C ® e
5.2 Beispiel
G = (T, N, P, S)
T = {X0, X1}
N = {a, b}, S= X0
P= {X0 ® X0b, X0 ® X1b, X1 ® X1a, X1 ® a}
Die von G erzeugte Sprache ist L(G) = {aibk | i, k > 0}
Bsp.
:
X0 ® X0b ® X1bb ® X1abb ® aabb
5.3 Endlicher Automat
Endliche Automaten nutzen Sprachen des Typs 3.
Definition: Ein endlicher Automat ist ein Sechstupel A = (I, O, Q, δ, q0, F), wobei
- I ist das Eingabealphabet (alle gültigen Eingabezeichen, die der Automat kennt),
- O ist das Ausgabealphabet (analog zu I),
- Q ist eine endliche, nichtleere Menge von Zuständen,
- q0 Î Q der Startzustand,
- δ: Q x I → Q x O die Zustandsübergangsfunktion mit einer Abbildung der Paare (q, i), wobei q Î Q ein Zustand ist und i Î I ein Eingabezeichen in ein Paar (q', o), wobei q' Î Q ein Folgezustand und o Î O ein Ausgabezeichen ist sowie
- F Í Q der Menge der Endzustände.
Anmerkung:
Die einzelnen hier aufgeführten Typen werden in den meisten Literaturquellen als Chomskytypen bezeichnet. Dies entspricht auch der Richtigkeit, jedoch habe ich hier aufgrund der Einfachheit das Chomsky weggelassen.
Noch kurz zur Sprache in diesem Zusammenhang.
Eine Sprache L Í T* ist von Chomsky-Typ-i(i=0,1,2,3), falls eine Chomsky-Grammatik G von diesem Typ i existiert, die diese Sprache erzeugt L = L(G). Die gängigen Programmiersprachen sind alle kontextfreie Sprachen (der Wichtigkeit und Vollständigkeit halber noch einmal).
Um bei der Vervollständigung zu bleiben. Die Vollständigkeit erlangt Chomsky-Lehre(Hierarchie), indem algorithmische Sprachklassen(Entscheidbarkeit) und die Klassen akzeptierender Automaten eingeordnet werden:
- aufzählbare Sprachen
- entscheidbare Sprachen
- reguläre Sprachen
(siehe 1)
Anlagen:
Sprach- und Automatenklassen
| Anmerkungen: |
| impressum | datenschutz
© Copyright Artikelpedia.com
