|
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)
5 |
