|
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 weder
geschrieben, verändert, noch überschritten werden.
|
