|
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*.
|
