Formale Sprachen und Automatentheorie 001

Formale Sprachen und Automatentheorie Udo Hebisch SS 2006 Dieses Skript enth¨alt nur den “roten Faden” der Vorlesung. Wesentliche Inhalte werden ausschließlich in der Vorlesung vermittelt. Daher ist dieses Skript nicht zum Selbststudium gedacht, sondern nur als “Erinnerungsstu ¨tze”.

1

1 FORMALE SPRACHEN Die Automatentheorie ist eine mathematische Theorie, die sich Verdienste um die Begriffsbildung und um die Aufdeckung der prinzipiellen M¨oglichkeiten erwarb. Sie hat enge Verbindung zur Theorie der formalen Sprachen und damit zu den Programmiersprachen. Sie soll nicht als praktikable Hilfswissenschaft f¨ ur konkrete Schaltwerke verstanden werden, sondern als eine Grundlagentheorie. Peter Deussen

1

Formale Sprachen

1.1

Freie Halbgruppen, Halbringe und Formale Sprachen

In der Automatentheorie und der Theorie formaler Sprachen werden einige Begriffe und Resultate u ¨ber Halbgruppen und Halbringe ben¨otigt. Sie werden daher hier zun¨achst einmal zusammengestellt. Umfangreichere Darstellungen der hier behandelten Zusammenh¨ange zwischen algebraischen Strukturen, Automatentheorie und formalen Sprachen findet man in den folgenden B¨ uchern: Peter Deussen, Halbgruppen und Automaten, Springer, Berlin 1971. Hartmut Ehrig, Michael Pfender, Kategorien und Automaten, DeGruyter, Berlin 1972. Jean Eric Pin, Varieties of Formal Languages, Plenum Press, New York 1986. Werner Kuich, Arto Salomaa, Semirings, Automata, Languages, Springer, Berlin 1986. Arto Salomaa, Matti Soittola, Automata-Theoretic Aspects of Formal Power Series, Springer, Berlin 1978. Definition 1.1 Unter einer Halbgruppe (S, ·) versteht man eine nichtleere Menge S zusammen mit einer bin¨aren Verkn¨ upfung (der Multiplikation) ·, die also je zwei Elementen a, b ∈ S genau ein Produkt a · b ∈ S zuordnet, so daß das Assoziativgesetz gilt: (1)

a · (b · c) = (a · b) · c

f¨ ur alle a, b, c ∈ S.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.1 Freie Halbgruppen, Halbringe und Formale Sprachen 1 FORMALE SPRACHEN

Besitzt die Halbgruppe ein Einselement e ∈ S gem¨aß (2)

e·a=a·e=a

f¨ ur alle a ∈ S,

so spricht man von einem Monoid. Gilt in (S, ·) das Kommutativgesetz (3)

a·b=b·a

f¨ ur alle a, b ∈ S,

so nennt man die Halbgruppe (das Monoid) kommutativ. Gilt (4)

a · a = a f¨ ur alle a ∈ S,

so heißt die Halbgruppe (das Monoid) idempotent. Einzelne Elemente a ∈ S, die (4) erf¨ ullen nennt man ebenfalls idempotent und man definiert E(S) = {a ∈ S | a · a = a}. Ein Element a ∈ S heißt linksk¨ urzbar [rechtsk¨ urzbar] in (S, ·), wenn (5)

a·x=a·y ⇒ x=y

[x · a = y · a ⇒ x = y]

f¨ ur alle x, y ∈ S gilt. Ist a sowohl links- als auch rechtsk¨ urzbar, so nennt man es k¨ urzbar. Sind alle Elemente a ∈ S einer Halbgruppe linksk¨ urzbar, rechtsk¨ urzbar oder k¨ urzbar, so nennt man die Halbgruppe linksk¨ urzbar, rechtsk¨ urzbar bzw. k¨ urzbar. Beispiel 1.2 F¨ ur jede Menge M 6= ∅ bildet die Menge TM = {f : M → M } aller Abbildungen (Transformationen) von M in sich mit der Nacheinanderanwendung von Abbildungen ein Monoid (TM , ◦), das Transformationsmonoid auf M . Dabei ist die identische Abbildung auf M Einselement. Definition 1.3 Unter einem Halbring (S, +, ·) versteht man zwei Halbgruppen (S, +) und (S, ·), so daß die beiden Distributivgesetze (6)

a · (b + c) = a · b + a · c und (a + b) · c = a · c + b · c

f¨ ur alle a, b, c ∈ S

erf¨ ullt sind. Ist (S, +) kommutativ [idempotent, k¨ urzbar], so nennt man den Halbring additiv kommutativ [additiv idempotent, additiv k¨ urzbar], ist (S, ·) kommutativ [idempotent], so nennt man den Halbring multiplikativ kommutativ [multiplikativ idempotent]. Ist (S, ·) ein Monoid, so nennt man das Einselement e von Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.1 Freie Halbgruppen, Halbringe und Formale Sprachen 1 FORMALE SPRACHEN

(S, ·) das Einselement des Halbringes (S, +, ·), ist (S, +) ein Monoid, so nennt man das Einselement o von (S, +) das Nullelement des Halbringes (S, +, ·). Ein Nullelement o, das noch (7)

a · o = o = o · a f¨ ur alle a ∈ S

erf¨ ullt, heißt absorbierend. Beispiel 1.4 a) Jeder Ring ist ein additiv kommutativer und k¨ urzbarer Halbring. Das Nullelement des Ringes ist stets absorbierend. b) Die nat¨ urlichen Zahlen bilden mit den u ¨blichen Operationen der Addition und Multiplikation einen Halbring (N0 , +, ·) mit absorbierendem Nullelement 0 und Einselement 1, der kein Ring ist. Dasselbe gilt f¨ ur (N, +, ·), wobei dieser Halbring kein Nullelement besitzt. Beide Halbringe sind additiv kommutativ und k¨ urzbar und multiplikativ kommutativ. c) Der zweielementige Verband (B, +, ·) = ({o, e}, ∨, ∧}) ist (wie jeder distributive Verband) ein additiv und multiplikativ kommutativer und idempotenter Halbring. Dies gilt ebenso f¨ ur den Verband (I, ∨, ∧) auf dem Einheitsintervall I mit den Operationen ∨ der Supremumsbildung und ∧ der Infimumsbildung. Man nennt (B, +, ·) auch den Booleschen Halbring. Diese Halbringe sind additiv idempotent und daher nicht k¨ urzbar. Sie sind auch multiplikativ idempotent. Genau dann besitzen sie ein absorbierendes Nullelement o, wenn sie (durch o) nach unten beschr¨ankt sind, und genau dann besitzen sie ein Einselement e, wenn sie (durch e) nach oben beschr¨ankt sind. Definition 1.5 Es seien (S, ·) und (T, ) zwei Halbgruppen. Eine Abbildung ϕ : S → T heißt ein (Halbgruppen-)Homomorphismus von (S, ·) in (T, ), wenn (8)

ϕ(a · b) = ϕ(a) ϕ(b)

f¨ ur alle a, b ∈ S gilt. Sind (S, +, ·) und (T, ⊕, ) zwei Halbringe, so heißt ϕ : S → T ein (Halbring-) Homomorphismus, wenn neben (8) noch (9)

ϕ(a + b) = ϕ(a) ⊕ ϕ(b)

f¨ ur alle a, b ∈ S gilt. Einen bijektiven (Halbgruppen- oder Halbring-) Homomorphismus nennt man einen Isomorphismus. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.1 Freie Halbgruppen, Halbringe und Formale Sprachen 1 FORMALE SPRACHEN ¨ Definition 1.6 Es sei (S, ·) eine Halbgruppe. Eine Aquivalenzrelation ∼ auf S heißt eine Linkskongruenz [Rechtskongruenz] auf (S, ·), wenn (10) x ∼ y ⇒ z · x ∼ z · y

[x ∼ y ⇒ x · z ∼ y · z]

f¨ ur alle x, y, z ∈ S erf¨ ullt ist. Sind beide Implikationen aus (10) erf¨ ullt, so nennt man ∼ eine Kongruenz(relation) auf (S, ·). Handelt es sich bei (S, +, ·) um einen Halbring und ist ∼ Linkskongruenz [Rechtskongruenz, Kongruenz] sowohl auf (S, +) als auch auf (S, ·), so spricht man von einer Linkskongruenz [Rechtskongruenz, Kongruenz] des Halbringes (S, +, ·). Beispiel 1.7 a) Jede Halbgruppe (S, ·) bzw. jeder Halbring (S, +, ·) besitzt die trivialen Kongruenzen ιS = {(a, a) | a ∈ S}, die identische Relation, und S × S, die Allrelation auf S. b) Ist ϕ : S → T Homomorphismus von (S, ·) in (T, ·) bzw. von (S, +, ·) in (T, +, ·), so wird durch (11) x ∼ y ⇐⇒ ϕ(x) = ϕ(y) f¨ ur alle x, y ∈ S eine Kongruenz auf (S, ·) bzw. (S, +, ·) definiert. Lemma 1.8 Ist ∼ Kongruenz auf einer Halbgruppe (S, ·) und bezeichnet S/ ∼= {[x] | x ∈ S} die Menge aller Restklassen [x] = {y ∈ S | y ∼ x}, dann wird durch (12) [x] · [y] = [x · y] f¨ ur alle [x], [y] ∈ S/ ∼ eine assoziative Multiplikation definiert. Daher ist (S/ ∼, ·) eine Halbgruppe, die Restklassenhalbgruppe von (S, ·) nach ∼. Die Abbildung ϕ : S → S/ ∼ mit ϕ(x) = [x] ist wegen (12) ein surjektiver Homomorphismus. Also ist mit (S, ·) auch (S/ ∼, ·) kommutativ bzw. idempotent. Ist e Einselement von (S, ·), so ist [e] Einselement von (S/ ∼, ·). Definition 1.9 Sind a und b Elemente einer Halbgruppe (S, ·) und ist c = a·b ihr Produkt, so nennt man a einen linken Teiler oder ein Pr¨afix und b einen rechten Teiler oder ein Postfix bzw. Suffix von c. Gilt c = adb, so nennt man d einen Teiler von c. Handelt es sich bei (S, ·) um ein Monoid mit dem Einselement e, so nennt man die Elemente, die gleichzeitig linke und rechte Teiler von e sind, die Einheiten von (S, ·). Mit U (S) wird die Menge aller Einheiten von (S, ·) bezeichnet (vgl. Aufgabe 1.58). Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.1 Freie Halbgruppen, Halbringe und Formale Sprachen 1 FORMALE SPRACHEN

Beispiel 1.10 In jedem Transformationsmonoid TM besteht die Menge U (TM ) genau aus den bijektiven Abbildungen auf M . Es handelt sich also dabei um die symmetrische Gruppe auf M . Beispiel 1.11 F¨ ur eine beliebige Menge X 6= ∅ sei X + = n∈N X n . Definiert man f¨ ur alle (x1 , . . . , xn ), (y1 , . . . , ym ) ∈ X + eine Multiplikation durch S

(13) (x1 , . . . , xn ) · (y1 , . . . , ym ) = (x1 , . . . , xn , y1 , . . . , ym ), dann ist (X + , ·) eine Halbgruppe, die freie Halbgruppe u ¨ber X. Man schreibt die + Elemente (x1 , . . . , xn ) ∈ X einfach in der Form x1 · · · xn und die Multiplikation als Konkatenation x1 · · · xn y1 · · · ym . Speziell f¨ ur endliches X nennt man X ein Alphabet, die Elemente x ∈ X Buchstaben und die Elemente x1 · · · xn ∈ X + W¨orter oder Strings u ¨ber X. Adjungiert man zu (X + , ·) ein leeres Wort  als Einselement, so nennt man X ∗ = X + ∪ {} das freie Monoid u ¨ber X. Sowohl (X + , ·) als auch (X ∗ , ·) sind k¨ urzbar. Genau die W¨orter u1 = x1 , u2 = x1 x2 , . . . , un−1 = x1 · · · xn−1 sind Pr¨afixe und die W¨orter v1 = x2 · · · xn , . . . , vn−1 = xn sind Postfixe von w. Ist w = x1 . . . xn ein Wort, so bezeichnet w = xn . . . x1 das gespiegelte Wort zu w. Unter einer formalen Sprache L (¨ uber dem Alphabet X) versteht man eine beliebige Teilmenge von X ∗ , also ein Element der Potenzmenge P(X ∗ ). F¨ ur jedes ∗ a ∈ X definiert man die Abbildung `a : X → N0 durch (14) `a (w) = `a (x1 . . . xn ) = |{i | xi = a}| f¨ ur alle w = x1 . . . xn ∈ X ∗ . Weiterhin sei ` : X ∗ → N0 durch `(w) = a∈X `a (w) f¨ ur alle w ∈ X ∗ definiert. Man nennt `(w) die L¨ange von w. Schließlich sei f¨ ur das Alphabet X = {a1 , . . . , ak } die Parikh-Abbildung Ψ : X ∗ → Nk0 durch P

(15) Ψ(w) = (`a1 (w), . . . , `ak (w)) festgelegt. Bemerkung 1.12 a) Die Abbildung `a z¨ahlt die Anzahl des Vorkommens des Buchstabens a ∈ X im Wort w ∈ X ∗ . Sie ist, ebenso wie die Abbildungen ` und Ψ, ein Homomorphismus. F¨ ur |X| = 1 stimmen alle diese Abbildungen u ¨berein und definieren einen Isomorphismus von (X ∗ , ·) auf (N0 , +). Man kann daher (N0 , +) als das (bis auf Isomorphie) eindeutig bestimmte freie Monoid u ¨ber einem einelementigen Alphabet auffassen. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.1 Freie Halbgruppen, Halbringe und Formale Sprachen 1 FORMALE SPRACHEN b) Betrachtet man die zur Parikh-Abbildung Ψ : X ∗ → Nk0 gem¨aß Bemerkung 1.7 geh¨orende Kongruenz, so nennt man Worte u, v ∈ X ∗ mit Ψ(u) = Ψ(v) symbol¨aquivalent, denn u und v bestehen (bis auf die Reihenfolge) aus denselben Buchstaben. Man nennt dann Sprachen L1 , L2 ⊆ X ∗ mit Ψ(L1 ) = Ψ(L2 ) ebenfalls symbol¨aquivalent. Definition 1.13 Sind (Si , i ) Halbgruppen f¨ ur eine beliebige Indexmenge I 6= ∅, dann wird auf dem kartesischen Produkt S = Πi∈I Si durch (16) (xi ) · (yi ) = (xi i yi ) f¨ ur alle (xi ), (yi ) ∈ S eine Multiplikation definiert. Man nennt (S, ·) das direkte Produkt der Halbgruppen (Si , i ). Bemerkung 1.14 Die in (16) definierte Multiplikation ist ersichtlich assoziativ, (S, ·) also eine Halbgruppe. Besitzt jede Halbgruppe (Si , i ) ein Einselement ei , so ist e = (ei ) Einselement von (S, ·). Sind alle (Si , i ) kommutativ [idempotent, k¨ urzbar], so gilt dasselbe f¨ ur (S, ·). Definition 1.15 Sind A und B Teilmengen einer Halbgruppe (S, ·) so versteht man unter dem Komplexprodukt AB die Teilmenge (17) AB = {a · b | a ∈ A, b ∈ B}. F¨ ur A = B schreibt man auch A2 anstelle von AA, f¨ ur einelementige Mengen A = {a} bzw. B = {b} schreibt man auch aB anstelle von {a}B bzw. Ab anstelle von A{b}. Definition 1.16 Neben den mengentheoretischen Operationen Durchschnitt ∩, Vereinigung ∪ und Komplement 0 existieren f¨ ur formale Sprachen K, L ∈ P(X ∗ ) noch die zweistellige Operation der Konkatenation K · L = KL gem¨aß (17) und S die einstellige ∗-Operation L∗ = n∈N0 Ln , wobei die Sprachen Ln rekursiv durch L0 = {ε} und Ln+1 = LLn definiert sind. Schließlich definiert man noch den Linksquotienten oder das Linksresiduum von L bez¨ uglich K durch (18) K −1 L = {w ∈ X ∗ | Kw ∩ L 6= ∅} und den Rechtsquotienten oder das Rechtsresiduum durch (19) LK −1 = {w ∈ X ∗ | wK ∩ L 6= ∅} Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.1 Freie Halbgruppen, Halbringe und Formale Sprachen 1 FORMALE SPRACHEN

Bemerkung 1.17 Die Operationen ∪ und ∩ sind sowohl kommutativ als auch idempotent, die Konkatenation ist nicht idempotent und nur f¨ ur |X| = 1 kommutativ (vgl. Aufgabe 1.62). Die Komplementbildung ist involutorisch, d. h. es gilt (A0 )0 = A f¨ ur alle A ⊆ X ∗ , die ∗-Operation ist nicht involutorisch. Die Quotienur einelementige Sprachen K = {x} tenbildung ist ersichtlich nicht kommutativ. F¨ schreibt man auch x−1 L statt {x}−1 L und Lx−1 statt L{x}−1 . Folgerung 1.18 Ist X ein Alphabet, so gilt f¨ ur die Potenzmenge P(X ∗ ) und die entsprechenden Operationen: a) (P(X ∗ ), ∪, ∩) ist ein sowohl additiv als auch multiplikativ kommutativer und idempotenter Halbring. Es ist X ∗ Einselement und ∅ absorbierendes Nullelement dieses Halbringes. b) (P(X ∗ ), ∪, ·) ist ein additiv, aber nicht multiplikativ idempotenter Halbring. W¨ahrend er auch stets additiv kommutativ ist, ist er f¨ ur |X| > 1 nicht multiplikativ kommutativ. Es ist {ε} Einselement und ∅ absorbierendes Nullelement dieses Halbringes. Beispiel 1.19 Beispiele f¨ ur Sprachen u ¨ber dem Alphabet X = {a, b}: a) L1 = {an | n ≥ 0} = {a}∗ ⊂ X ∗ , b) L2 = {a(2

n)

| n ≥ 1}.

c) L3 = {(ab)n | n ≥ 1} = {ab}+ . d) L4 = {an bm | n, m ≥ 1} = {a}+ {b}+ . e) L5 = {an bn | n ≥ 1} ⊂ L4 . f) L6 = {an bam | n, m ≥ 0} = L1 {b}L1 . g) L7 = {an ban | n ≥ 0} ⊂ L6 . h) L8 = {an bn an | n ≥ 2}. i) L9 = L5 L5 . Definition 1.20 Es sei (S, +, ·) ein additiv kommutativer Halbring mit einem absorbierenden Nullelement o und einem Einselement e. Weiterhin sei X ein

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.1 Freie Halbgruppen, Halbringe und Formale Sprachen 1 FORMALE SPRACHEN

Alphabet. Unter einer formalen Potenzreihe f u ¨ber S in den Unbestimmten xi ∈ ∗ X versteht man dann eine Abbildung f : X → S mit f (w) = αw ∈ S, die gem¨aß X

f=

αw w

w∈X ∗

geschrieben wird. Dabei heißt αw ∈ S der Koeffizient von f an der Stelle w ∈ X ∗ und supp(f ) = {w ∈ X ∗ | αw 6= o} der Support oder Tr¨ager von f . Ist der Tr¨ager von f endlich, so spricht man auch von einem Polynom f . Gilt sogar supp(f ) ⊆ {ε}, so heißt das Polynom f konstant. Die Menge aller derartigen Potenzreihen wird mit S[[X]] bezeichnet, die Teilmenge aller Polynome mit S[X]. P

F¨ ur Potenzreihen f = w∈X ∗ αw w und g = f + g elementweise durch X

f +g =

P

w∈X ∗

βw w definiert man die Summe

(αw + βw )w

w∈X ∗

und das Produkt f g als Cauchyprodukt gem¨aß !

fg =

X

X

w∈X ∗

uv=w

αu βv w.

Bemerkung 1.21 a) Ist X = {x} einelementig und S = R ein Ring, dann ist R[x] = R[{x}] der gew¨ohnliche Polynomring u ¨ber R und beispielsweise R[[x]] der aus der Analysis bekannte Ring der (formalen) Potenzreihen u ¨ber den reellen Zahlen. b) Ist S = B der Boolesche Halbring, so kann man jedes f ∈ B[[X]] als charakteristische Funktion einer Teilmenge von X ∗ auffassen. Jede formale Potenzreihe entspricht dann umkehrbar eindeutig einer formalen Sprache und umgekehrt. Diese Identifikation er¨offnet einen ersten Zugang zu einer algebraischen Untersuchung formaler Sprachen. Im Hinblick auf den n¨achsten Satz entspricht der Halbring (B[[X]], +, ·) n¨amlich genau dem Halbring (P(X ∗ ), ∪, ·) aus Folgerung 1.18 b). Satz 1.22 Es sei (S, +, ·) ein additiv kommutativer Halbring mit einem absorbierenden Nullelement o und einem Einselement e. Weiterhin sei X ein Alphabet. Dann bildet die Menge aller formalen Potenzreihen u ¨ber S in den Unbestimmten aus X einen additiv kommutativen Halbring (S[[X]], +, ·) mit absorbierendem Nullelement o und Einselement e. Er enth¨alt die Polynome als Unterhalbring und darin den Halbring (S, +, ·) in Form der konstanten Polynome wiederum als Unterhalbring. Genau dann ist (S[[X]], +, ·) (und damit (S[X], +, ·)) additiv idempotent bzw. k¨ urzbar, wenn dies auf (S, +, ·) zutrifft. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.2 Regul¨are, rationale und erkennbare Sprachen 1 FORMALE SPRACHEN

1.2

Regul¨ are, rationale und erkennbare Sprachen

Definition 1.23 Es sei X ein Alphabet. Durch die folgenden Festlegungen werden regul¨are Ausdr¨ ucke α und die ihnen zugeordneten regul¨aren Sprachen L(α) ⊆ ∗ X definiert. (1) ∅ ist ein regul¨arer Ausdruck u ¨ber X mit L(∅) = ∅. (2) ε ist ein regul¨arer Ausdruck u ¨ber X mit L(ε) = {ε}. (3) F¨ ur jedes x ∈ X ist x ein regul¨arer Ausdruck u ¨ber X mit L(x) = {x}. (4) Sind α und β regul¨are Ausdr¨ ucke u ¨ber X, so auch α ∪ β mit L(α ∪ β) = L(α) ∪ L(β) und αβ mit L(αβ) = L(α)L(β). (5) Ist α regul¨arer Ausdruck u ¨ber X, dann auch α∗ mit L(α∗ ) = L(α)∗ . Nur die nach (1) - (5) erzeugbaren Ausdr¨ ucke bzw. formalen Sprachen sind regul¨ar. Zwei regul¨are Ausdr¨ ucke α und β mit L(α) = L(β) heißen ¨aquivalent. Bemerkung 1.24 a) Zur Vereinfachung regul¨arer Ausdr¨ ucke vereinbart man noch, daß die ∗-Operation h¨ochste Priorit¨at besitzt, danach kommt die Konkatenation, zuletzt die Vereinigung. b) Nach der obigen Definition sind beispielsweise die regul¨aren Ausdr¨ ucke α = ∗ ∗ ((a ∪ ε)a) und β = a u ¨ber X = {a} ¨aquivalent. Die ihnen zugeordnete regul¨are Sprache ist L(α) = {a}∗ = L1 aus Beispiel 1.19. c) Es gibt Algorithmen, die f¨ ur beliebige regul¨are Sprachen L1 und L2 u ¨ber X und beliebiges x ∈ X ∗ entscheiden, ob gilt: (1) x ∈ L1 (Wortproblem), (2) L1 = ∅ (Leerheitsproblem) (vgl. Folgerung 6.3), (3) |L1 | endlich (Endlichkeitsproblem), (4) L1 ∩ L2 = ∅ (Durchschnittsproblem), ¨ (5) L1 = L2 (Aquivalenzproblem). d) F¨ ur jeden regul¨aren Ausdruck α u ¨ber X und jedes w ∈ X ∗ ist das Wortproblem w ∈ L(α) in O(`(α)`(w)) Schritten entscheidbar. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.2 Regul¨are, rationale und erkennbare Sprachen 1 FORMALE SPRACHEN

Definition 1.25 Sind f, g : N0 → C Funktionen, so schreibt man f (n) = O(g(n)), wenn es ein c > 0 und ein n0 ∈ N0 gibt, so daß |f (n)| ≤ cg(n) f¨ ur alle n ≥ n0 gilt. Satz 1.26 Sind L1 und L2 regul¨are Sprachen u ¨ber X ∗ , dann sind auch die folgenden Sprachen regul¨ar: (1) L1 ∪ L2 , (2) L1 L2 , (3) L∗1 , ∗ (4) L+ 1 = L1 L 1 ,

(5) L01 = X ∗ \ L1 , (6) L1 ∩ L2 , (7) L1 \ L2 , (8) L1 (vgl. Aufgabe 1.61). Beweisidee: (1) - (4) folgen unmittelbar aus Definition 1.23. (5) l¨aßt sich mit Hilfe erkennender Monoide f¨ ur regul¨are Sprachen beweisen (vgl. Bemerkung 1.28 b, Satz 1.34 und Folgerung 1.31 a)). (6) folgt dann aus (1) und (5) mit den DeMorganschen Regeln. (7) folgt aus (5) und (6) wegen L1 \ L2 = L1 ∩ (X ∗ \ L2 ). (8) folgt aus Aufgabe 1.61. Wegen dieser Abgeschlossenheit gegen¨ uber den “einfachen” Rechenoperationen hat man auch eine andere Bezeichnungsweise f¨ ur regul¨are Sprachen. Definition 1.27 Es sei X ein Alphabet. Die Menge Rat(X ∗ ) aller rationalen Sprachen von X ∗ ist die kleinste Teilmenge von P(X ∗ ), die alle einelementigen Sprachen {x} f¨ ur x ∈ X ∗ enth¨alt und die abgeschlossen ist gegen¨ uber endlichen Vereinigungen, Produkten und der ∗-Operation.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.2 Regul¨are, rationale und erkennbare Sprachen 1 FORMALE SPRACHEN Bemerkung 1.28 a) F¨ ur X = {a, b} liegen jedenfalls die Sprachen L1 = {a}∗ und L6 = L1 {b}L1 aus Beispiel 1.19 in Rat(X ∗ ). b) Jede endliche Sprache ist als endliche Vereinigung von einelementigen Sprachen rational. Also gilt auch X ∈ Rat(X ∗ ) und damit X ∗ ∈ Rat(X ∗ ). Schließlich betrachtet man auch die leere Sprache ∅, die man als “leere” (endliche) Vereinigung auffaßt, als zu Rat(X ∗ ) geh¨orig. Daher sind die rationalen Sprachen genau die regul¨aren Sprachen gem¨aß Definition 1.23. b) (Rat(X ∗ ), ∪, ·) ist der kleinste Unterhalbring von (P(X ∗ ), ∪, ·) (oder wegen Bemerkung 1.21 b) von (B[[X]], +, ·)), der die einelementigen Sprachen (oder der (B[X], +, ·)) enth¨alt und der abgeschlossen gegen¨ uber der ∗-Operation ist. Dies er¨offnet einen algebraischen Zugang zu dieser Sprachklasse. Einen andereren algebraischen Zugang zu einer auf den ersten Blick anderen Sprachklasse (vgl. aber Satz 1.34), liefern die folgenden Definitionen. Definition 1.29 Es seien X ein Alphabet, L ⊆ X ∗ und (M, ·) ein Monoid. Man sagt (M, ·) erkennt L, wenn es einen Homomorphismus ϕ : X ∗ → M und eine Menge P ⊆ M gibt, so daß L = ϕ−1 (P ) gilt. Die Sprache L heißt erkennbar, wenn es ein endliches Monoid gibt, das L erkennt. Mit Rec(X ∗ ) werde die Menge aller erkennbaren Sprachen aus X ∗ bezeichnet. Bemerkung 1.30 a) Jede Sprache L ⊆ X ∗ wird durch das Monoid (X ∗ , ·) erkannt, man muß nur ϕ als identische Abbildung und P = L w¨ahlen. Bei der Erkennbarkeit einer Sprache spielt also die Endlichkeit des Monoids die entscheidende Rolle. b) Da ersichtlich X ∗ homomorph auf das einelementige Monoid ({1}, ·) abgebildet werden kann, gilt jedenfalls X ∗ ∈ Rec(X ∗ ) 6= ∅. Folgerung 1.31 Es seien X ein Alphabet und L ⊆ X ∗ . a) Erkennt ein Monoid (M, ·) die Sprache L, dann erkennt (M, ·) auch X ∗ \ L. Die Menge Rec(X ∗ ) ist also abgeschlossen gegen¨ uber der Komplementbildung. b) Erkennt ein Monoid (M, ·) die Sprache L und ist K ⊆ X ∗ eine weitere Sprache, dann erkennt (M, ·) auch K −1 L und LK −1 . Folgerung 1.32 Sind L1 und L2 Sprachen u ¨ber dem Alphabet X, die von den Monoiden M1 bzw. M2 erkannt werden, dann werden die Sprachen L1 ∪ L2 und L1 ∩ L2 von dem Monoid M1 × M2 erkannt. Insbesondere ist Rec(X ∗ ) auch abgeschlossen gegen¨ uber endlichen Vereinigungen und Durchschnitten, also eine Boolesche Algebra. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.3 Automaten

1 FORMALE SPRACHEN

Folgerung 1.33 Es seien X und Y Alphabete und ψ : X ∗ → Y ∗ ein Homomorphismus. Wird die Sprache L ⊆ Y ∗ durch das Monoid M erkannt, dann erkennt M auch ψ −1 (L) ⊆ X ∗ . Der folgende Satz geht auf S. C. Kleene in seinem Artikel “Representation of events in nerve nets and finite automata”, C. E. Shannon, J. McCarthy (Hrsg.), Automata Studies, Princeton University Press, Princeton 1959, zur¨ uck. Satz 1.34 (S. C. Kleene) F¨ ur jedes Alphabet X gilt Rec(X ∗ ) = Rat(X ∗ ).

1.3

Automaten

Die Theorie formaler Sprachen h¨angt eng mit der Theorie der Automaten zusam¨ men, wie bereits in den folgenden Uberlegungen deutlich wird. Definition 1.35 Unter einem endlichen Automaten versteht man im allgemeinen ein 5-Tupel A = (Q, X, δ, Qf , Qs ), bestehend aus einer endlichen Menge Q von Zust¨anden, einer nichtleeren Teilmenge Qs ⊆ Q von Startzust¨anden, einer (m¨oglicherweise leeren) Teilmenge Qf ⊆ Q von Endzust¨anden, einem endlichen Eingabealphabet X mit X ∩ Q = ∅ und ei¨ ner Ubergangsrelation δ ⊆ Q × (X ∪ {ε}) × Q, wobei ε das leere Wort u ¨ber X bezeichnet. Bemerkung 1.36 Je nach zus¨atzlichen Bedingungen an die einzelnen Komponenten des Automaten unterscheidet man verschiedene Automatenklassen. Gilt etwa |Qs | = 1, so spricht man von initialen endlichen Automaten, bei |Qs | = k > 1 von k-Eingangsautomaten. Existiert wenigstens ein Tripel (q, ε, q 0 ) ∈ δ mit q 6= q 0 , so nennt man A einen ε-Automaten, gilt |{(q, x, q 0 ) ∈ δ}| ≤ 1 f¨ ur alle (q, x) ∈ Q × X und ist A kein ε-Automat, so heißt A ein deterministischer endlicher Automat usw. In der folgenden alternativen Definition dieser einfachsten Klasse von Automaten sind die Angaben u ¨ber Start- und Endzust¨ande zun¨achst noch weggelassen. Definition 1.37 Ein (deterministischer, endlicher) Automat A = (Q, X, ·) besteht aus einer endlichen Menge Q von Zust¨anden, einem Alphabet X und einer Operatoranwendung · : Q × X → Q, die f¨ ur jeden Buchstaben x ∈ X zu jedem Zustand q ∈ Q den Folgezustand q · x ∈ Q festlegt. Man erweitert die Operatoranwendung von Q × X auf Q × X ∗ , indem man f¨ ur alle q ∈ Q, w ∈ X ∗ und x ∈ X definiert: q · ε = q und q · (wx) = (q · w) · x. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.3 Automaten

1 FORMALE SPRACHEN

Bemerkung 1.38 a) Jedes Wort w ∈ X ∗ vermittelt also eine Transformation tw : Q → Q der Menge der Zust¨ande des Automaten in sich. Die Menge aller derartigen Transformationen bildet offensichtlich ein Untermonoid M (A) des vollen Transformationsmonoids TQ . Dieses Monoid wird auch Transitionsmonoid des Automaten genannt. Man kann einen Automaten daher durch eine Tabelle der Transformationen tx f¨ ur x ∈ X beschreiben. b) Auch durch einen Graphen l¨aßt sich ein Automat A = (Q, X, ·) beschreiben: Zu jedem Zustand q ∈ Q geh¨ort ein Knoten des Graphen, und eine gerichtete Kante f¨ uhrt genau dann von einem Knoten q zu einem Knoten q 0 , wenn ein x ∈ X mit q · x = q 0 existiert. Man markiert diese Kante dann mit dem Buchstaben x. Beispiel 1.39 Der Automat A = (Q, X, ·) sei gegeben durch Q = {1, 2, 3}, X = {a, b} und die Operatoranwendung 1 · a = 2, 1 · b = 2 · b = 1, 2 · a = 3 · a = 3 · b = 3. Die zugeh¨orige Automatentafel ist dann · 1 2 3 ta 2 3 3 tb 1 1 3 Das vollst¨andige Transitionsmonoid ergibt sich zu · tε ta tb taa tab tba

1 1 2 1 3 1 2

2 2 3 1 3 3 2

3 3 3 3 3 3 3

Der zugeh¨orige Graph ist a

b 1

a

b

2

a

3

b

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.3 Automaten

1 FORMALE SPRACHEN

Definition 1.40 Es seien L ⊆ X ∗ eine Sprache und A = (Q, X, ·) ein Automat. Man sagt, daß L von A erkannt wird, wenn es einen Zustand q0 ∈ Q, den Anfangszustand, und eine Menge F ⊆ Q von Endzust¨anden gibt, so daß w ∈ L genau dann gilt, wenn q0 · w ∈ F gilt. Beispiel 1.41 Ist A = (Q, X, ·) der Automat aus Beispiel 1.39 und q1 der Anfangszustand, so wird f¨ ur F = {q1 } die Sprache L1 = {b}∗ {a{b}+ }∗ erkannt, f¨ ur ∗ F = {q2 } die Sprache L2 = L1 {a} und f¨ ur F = {q3 } die Sprache L3 = X {aa}X ∗ . Bemerkung 1.42 a) Die Betrachtung “unendlicher” Automaten zur Erkennung ¨ von Sprachen macht wenig Sinn, wie die folgende Uberlegung zeigt. Es sei L ⊆ X ∗ eine beliebige Sprache u ¨ber dem (endlichen) Alphabet X. Definiere den “Automaten” A = (Q, X, ·) mit der abz¨ahlbar unendlichen Zustandsmenge Q = X ∗ und der Operatoranwendung · : X ∗ × X ∗ → X ∗ als Konkatenation gem¨aß u · v = uv. F¨ ur den Anfangszustand q0 = ε und die Menge F = L von Endzust¨anden wird dann genau die Sprache L erkannt. b) Oft werden endliche Automaten auch endliche (deterministische) Akzeptoren genannt und in der Form A = (Q, X, ·, q0 , F ) mit den Bedeutungen aus Definition 1.40) definiert. Sie “akzeptieren” dann genau die Worte w ∈ X ∗ , f¨ ur die q0 w ∈ F gilt. Manche Autoren nennen A = (Q, X, ·, q0 ) dann auch einen initialen endlichen Automaten. b) Ist A = (Q, X, ·) ein Automat, der mit dem Anfangszustand q0 ∈ Q und den Endzust¨anden F ⊆ Q die Sprache L ⊆ X ∗ erkennt, so erkennt A mit demselben Anfangszustand und der Menge Q \ F offensichtlich die Sprache X ∗ \ L. Satz 1.43 Wird eine Sprache L von einem Automaten A = (Q, X, ·) erkannt, so wird sie auch von dem Transitionsmonoid M (A) erkannt. Eine Sprache ist genau dann erkennbar, wenn sie von einem endlichen Automaten erkannt wird. Definition 1.44 Ist A = (Q, X, ·) ein Automat und q0 ∈ Q ein ausgezeichneter Anfangszustand, so heißt ein Zustand q ∈ Q erreichbar, wenn es ein w ∈ X ∗ mit q = q0 ·w gibt. Der Automat A heißt vereinfacht (bez¨ uglich des Anfangszustandes q0 ), wenn alle Zust¨ande erreichbar sind. Ist weiterhin F ⊆ Q eine ausgezeichnete Menge von Endzust¨anden, so heißen zwei Zust¨ande q, q 0 ∈ Q ¨aquivalent, in Zeichen q ∼ q 0 , wenn f¨ ur alle w ∈ X ∗ gilt q · w ∈ F ⇐⇒ q 0 · w ∈ F . Der Automat A = (Q, X, ·) mit Startzustand q0 und Endzust¨anden F heißt reduziert, wenn alle Zust¨ande erreichbar sind und wenn aus q ∼ q 0 stets q = q 0 folgt. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.3 Automaten

1 FORMALE SPRACHEN

Beispiel 1.45 Der Automat A = (Q, X, ·) sei gegeben durch Q = {1, 2}, X = {a} und die Operatoranwendung 1 · a = 2 · a = 2. F¨ ur q0 = 1 sind alle Zust¨ande erreichbar, f¨ ur q0 = 2 ist nur der Zustand 2 erreichbar. Ist q0 = 1 Anfangszustand, so sind f¨ ur F = {1, 2} oder f¨ ur F = ∅ beide Zust¨ande ur F = {1} oder f¨ ur F = {2} beide Zust¨ande in¨aquivalent. Die ¨aquivalent, f¨ erkannten Sprachen sind der Reihe nach X ∗ , ∅, {ε} und X + . Im ersten und zweiten Fall kann man A zu dem Automaten A0 = ({1}, {a}, ) mit 1 a = 1 reduzieren (vgl. Satz 1.47). Bemerkung 1.46 Offenbar k¨onnen unerreichbare Zust¨ande aus der Zustandsmenge eines Automaten A entfernt werden, ohne daß, bei gleichem Startzustand, die erkannte Sprache ge¨andert wird. ¨ Die Relation ∼ ist eine Aquivalenzrelation auf der Menge der Zust¨ande eines endlichen Automaten. Satz 1.47 Ist A = (Q, X, ·) ein Automat, der mit dem Startzustand q0 ∈ Q und den Endzust¨anden F die Sprache L erkennt, dann gibt es einen reduzierten Automaten A0 = (Q0 , X, ), der mit dem Startzustand q00 ∈ Q0 und den Endzust¨anden F 0 ⊆ Q0 ebenfalls L erkennt. Definition 1.48 Es seien A = (Q, X, ·) und A0 = (Q0 , X, ) zwei Automaten. Man nennt A0 ein homomorphes Bild von A, wenn es eine surjektive Abbildung ϕ : Q → Q0 gibt, die mit den Operatoranwendungen in der folgenden Weise vertr¨aglich ist. (20) ϕ(q · x) = ϕ(q) x f¨ ur alle x ∈ X. Ist ϕ sogar bijektiv, dann heißen die beiden Automaten isomorph zueinander. Sind f¨ ur die beiden Automaten noch Startzust¨ande q0 ∈ Q und q00 ∈ Q0 und Endzust¨ande F ⊆ Q sowie F 0 ⊆ Q0 spezifiziert, so verlangt man u ¨ber (20) hinaus noch (21) ϕ(q0 ) = q00 und (22) q ∈ F ⇐⇒ ϕ(q) ∈ F 0 . Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.3 Automaten

1 FORMALE SPRACHEN

Bemerkung 1.49 a) Sind A = (Q, X, ·) und A0 = (Q0 , X, ) wie in Definition 1.48 mit den jeweils spezifizierten Start- bzw. Endzust¨anden, so erkennen beide Automaten dieselbe Sprache. b) Sind A = (Q, X, ·) und A0 = (Q0 , X, ) Automaten wie in Satz 1.47, so ist A0 homomorphes Bild von A. In diesem Sinne ist A0 minimaler Automat, der L erkennt. Der Homomorphismus ϕ ist durch die Forderung ϕ(q0 ) = q00 eindeutig bestimmt. Mit dem folgenden Algorithmus wird zu einer gegebenen Sprache L ⊆ X ∗ ein (Minimal-)automat A = (Q, X, ·) konstruiert, der (bei geeignetem Anfangszustand und geeigneten Endzust¨anden) L erkennt. Zuerst werden die Zust¨ande berechnet. Diese sind Teilmengen von X ∗ . 1. Beginne mit Q = {q = L} (als sp¨aterem Startzustand). 2. F¨ ur alle x ∈ X und alle (neu hinzugekommenen) Zust¨ande q ∈ Q berechne q 0 = x−1 q ⊆ X ∗ . 3. Alle noch nicht in Q vorhandenen q 0 nehme neu in Q auf. 4. Falls keine neuen Zust¨ande hinzugenommen wurden, ist Q die endg¨ ultige Zustandsmenge, sonst mache weiter bei 2. Die Operatoranwendung wird nun folgendermaßen festgelegt: F¨ ur x ∈ X und q = A ∈ Q setze q · x = A · x = x−1 A = q 0 . Es gilt also Q = {w−1 L | w ∈ X ∗ } und (w−1 L) · x = x−1 (w−1 L) = (wx)−1 L f¨ ur alle x ∈ X. Die Endzust¨ande zur Erkennung von L sind F = {w−1 L | w ∈ L}. Beispiel 1.50 Bestimmung des Minimalautomaten f¨ ur L = X ∗ aaX ∗ u ¨ber X = {a, b}. 1. Setze q1 = L. 2. Berechne a−1 L = L ∪ aX ∗ = q2 und b−1 L = L = q1 . 3. Bestimme neu Q = {q1 , q2 }. 4. Mache weiter bei 2. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.4 Syntaktische Monoide

1 FORMALE SPRACHEN

2. Berechne a−1 (L ∪ aX ∗ ) = a−1 L ∪ a−1 (aX ∗ ) = L ∪ aX ∗ ∪ X ∗ = X ∗ = q3 und b−1 (L ∪ aX ∗ ) = b−1 L ∪ b−1 (aX ∗ ) = L ∪ ∅ = L = q1 . 3. Bestimme neu Q = {q1 , q2 , q3 }. 4. Mache weiter bei 2. 2. Berechne a−1 X ∗ = X ∗ = q3 und b−1 X ∗ = X ∗ = q3 . 3. Q ¨andert sich nicht mehr. Es ergibt sich (bis auf die andere Bezeichnung der Zust¨ande) der Automat aus Beispiel 1.39.

1.4

Syntaktische Monoide

Satz 1.51 Es sei L ⊆ X ∗ eine Sprache. Die durch u ∼L v ⇐⇒ (xuy ∈ L ⇔ xvy ∈ L) f¨ ur alle u, v, x, y ∈ X ∗ definierte Relation ist eine Kongruenzrelation auf (X ∗ , ·). S Es ist L eine Vereinigung von Kongruenzklassen, n¨amlich L = x∈L [x]∼L . Definition 1.52 Die Relation ∼L heißt syntaktische Kongruenz von L und das Restklassenmonoid M (L) = X ∗ / ∼L heißt syntaktisches Monoid von L. Definition 1.53 Eine Halbgruppe (S, ·) teilt die Halbgruppe (T, ·), in Zeichen: S < T , wenn es eine Unterhalbgruppe (T 0 , ·) von (T, ·) und einen surjektiven Homomorphismus ϕ : T 0 → S gibt. Satz 1.54 Es seien L ⊆ X ∗ eine Sprache und M, N Monoide. Dann gelten (1) M erkennt L genau dann, wenn M (L) < M gilt. (2) Wenn L von M erkannt wird und M < N gilt, so wird L auch von N erkannt. Bemerkung 1.55 Eine Sprache L ⊆ X ∗ ist also genau dann erkennbar, wenn es eine Kongruenz ∼ auf (X ∗ , ·) und endlich viele W¨orter w1 , . . . , wn ∈ X ∗ gibt, so daß X ∗ / ∼ endlich ist und L = [w1 ]∼ ∪ . . . ∪ [wn ]∼ gilt. In diesem Fall ist die syntaktische Kongruenz ∼L eine derartige Kongruenz. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.5 Aufgaben

1 FORMALE SPRACHEN

Folgerung 1.56 Es seien L, L1 , L2 ⊆ X ∗ erkennbare Sprachen und K ⊆ X ∗ eine beliebige Sprache. Dann gilt f¨ ur die syntaktischen Monoide (1) M (X ∗ \ L) ∼ = M (L), (2) M (L1 ∩ L2 ) < M (L1 ) × M (L2 ), (3) M (L1 ∪ L2 ) < M (L1 ) × M (L2 ), (4) M (K −1 L) < M (L) und M (LK −1 ) < M (L), (5) M (ϕ−1 (L)) < M (L) f¨ ur jeden Homomorphismus ϕ : Y ∗ → X ∗ .

1.5

Aufgaben

Aufgabe 1.57 Ein Einselement eines Monoids ist eindeutig bestimmt. Daher gilt dasselbe f¨ ur das Nullelement eines Halbringes. Ein Element e ∈ S einer Halbgruppe (S, ·) ist genau dann ein Einselement, wenn es idempotent und k¨ urzbar in (S, ·) ist. Daher besteht eine idempotente und gleichzeitig k¨ urzbare Halbgruppe aus genau einem Element. Aufgabe 1.58 In jedem Monoid (S, ·) bildet die Menge U (S) der Einheiten eine Untergruppe. Aufgabe 1.59 Ein Wort w ∈ X ∗ heißt ein Palindrom, wenn w = w gilt. Die formale Sprache L ⊆ X ∗ sei durch L = {ww | w ∈ X ∗ } definiert. Beweisen oder widerlegen Sie: L besteht genau aus den Palindromen. Aufgabe 1.60 Untersuchen Sie die Sprachen aus Beispiel 1.19 auf Symbol¨aquivalenz. Aufgabe 1.61 Zu jedem regul¨aren Ausdruck α u ¨ber X gebe man einen regul¨aren Ausdruck α an mit L(α) = {w | w ∈ L(α)}. Aufgabe 1.62 F¨ ur alle W¨orter x, y ∈ X + sind folgende Bedingungen gleichwertig: a) xy = yx, b) es gibt n, m > 0 mit xm = y n , c) es gibt ein z ∈ X + und k, l > 0 mit x = z k , y = z l . Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

1.5 Aufgaben

1 FORMALE SPRACHEN

Aufgabe 1.63 Es sei X ein Alphabet. F¨ ur a ∈ X, v, w ∈ X ∗ und K, L ⊆ X ∗ gelten: a) w−1 (K ∪ L) = w−1 K ∪ w−1 L, b) w−1 (K \ L) = w−1 K \ w−1 L, c) w−1 (K ∩ L) = w−1 K ∩ w−1 L, d) a−1 (KL) = (a−1 K)L, falls ε ∈ / K, und a−1 (KL) = (a−1 K)L ∪ a−1 L, falls ε ∈ K. e) a−1 L∗ = (a−1 L)L∗ , f) v −1 (w−1 L) = (wv)−1 L. Aufgabe 1.64 Zu den folgenden Sprachen L u ¨ber dem jeweils angegebenen Alphabet X ist der Minimalautomat zu bestimmen. a) X = {a, b}, L = {ab}. b) X = {a, b}, L = X ∗ a. c) X = {a, b}, L = X ∗ abX ∗ . d) X = {a, b, c}, L = X ∗ abX ∗ . e) X = {a, b}, L = {ab}∗ . Aufgabe 1.65 Es sei (S, ·) eine Halbgruppe und L ⊆ S. Die durch u ∼L v ⇐⇒ (xuy ∈ L ⇔ xvy ∈ L) f¨ ur alle u, v, x, y ∈ S definierte Relation ist eine Kongruenzrelation auf (S, ·). Handelt es sich bei (S, ·) um ein Monoid, so ist L eine Vereinigung von KongruS enzklassen, n¨amlich L = x∈L [x]∼L . Aufgabe 1.66 Zeigen Sie, daß die Teilbarkeitsrelation f¨ ur Halbgruppen reflexiv und transitiv ist. Aufgabe 1.67 Beweisen Sie die Behauptungen aus Bemerkung 1.55.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

2

Regelgrammatiken und Regelsprachen

Im Jahr 1914 f¨ uhrte der norwegische Mathematiker Axel Thue (1863 - 1922) die heute nach ihm benannten Systeme zur Manipulation von Zeichenketten u ¨ber einem beliebigen Alphabet ein. Dabei ging es ihm vor allem um die Untersuchung von Wortproblemen. Hierauf aufbauend f¨ uhrte dann der Linguist Noam Chomsky in den Jahren 1959 - 1963 eine ganze Hierarchie solcher Systeme ein, die heute Regelgrammatiken verschiedenen Typs genannt werden. Chomsky wollte mit ihnen die Grammatiken nat¨ urlicher Sprachen formalisieren und n¨aher untersuchen.

Definition 2.1 Ein Produktionssystem oder Semi-Thue-System P = (X, R) besteht aus einem Alphabet X und einer nichtleeren, endlichen Menge R ⊂ X ∗ ×X ∗ von Produktionsregeln. Die Elemente (u, v) ∈ R nennt man auch definierende Relationen und schreibt sie in der Form u → v. Das Produktionssystem heißt ein Thue-System, wenn die Relation R symmetrisch ist, wenn also mit u → v stets auch v → u gilt. Definition 2.2 Es sei P = (X, R) ein Produktionssystem. F¨ ur W¨orter x, y ∈ X ∗ definiert man die Relation x → y, wenn es W¨orter z1 , z2 ∈ X ∗ und eine Regel u → v aus R gibt, so daß x = z1 uz2 und y = z1 vz2 gelten. Weiterhin soll die Relation x →∗ y genau dann gelten, wenn es endlich viele W¨orter w0 , w1 , . . . , wn (n ≥ 1) aus X ∗ mit x = w0 , wn = y und wi−1 → wi f¨ ur i = 1, . . . , n gibt. Man sagt dann, y sei aus x durch P in n Schritten ableitbar oder x sei in y u uhrbar. Eine ¨berf¨ derartige Ableitung heißt minimal, wenn die W¨orter wi paarweise verschieden sind. Bemerkung 2.3 a) Die Ableitbarkeitsrelation →∗ auf X ∗ ist ersichtlich reflexiv und transitiv und es gilt f¨ ur alle x, y, u, v ∈ X ∗ (23) x →∗ y, u →∗ v =⇒ xu →∗ yv. b) F¨ ur ein Thue-System ist →∗ auch symmetrisch und wegen (23) daher eine Kongruenzrelation auf dem Monoid (X ∗ , ·). Also existiert das Restklassenmonoid X ∗ / →∗ . c) Unter dem Wortproblem f¨ ur ein Semi-Thue-System P versteht man das Problem, einen Algorithmus zu finden, der f¨ ur beliebige W¨orter x, y ∈ X ∗ in endlich vielen Schritten entscheidet, ob x →∗ y gilt oder nicht. Das allgemeine Wortproblem f¨ ur Semi-Thue-Systeme ist die Frage nach einem Algorithmus, der f¨ ur jedes Semi-Thue-System diese Entscheidung in endlich vielen Schritten findet. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

d) F¨ ur Thue-Systeme l¨auft das Wortproblem darauf hinaus zu entscheiden, ob f¨ ur zwei beliebige W¨orter x, y ∈ X ∗ in dem Restklassenmonoid X ∗ / →∗ bereits [x] = [y] gilt. e) Man kann zeigen, daß das allgemeine Wortproblem sowohl f¨ ur Semi-ThueSysteme als auch f¨ ur Thue-Systeme unl¨osbar ist. Weiterhin kann man sogar konkrete Semi-Thue-Systeme und Thue-Systeme angeben, f¨ ur die das jeweilige Wortproblem unl¨osbar ist. Einen Beweis findet man etwa in Hans Hermes, Aufz¨ahlbarkeit, Entscheidbarkeit, Berechenbarkeit, Springer-Verlag, Berlin 1971. Dort finden sich auch Literaturangaben zu zahlreichen Originalarbeiten aus diesem Problemkreis. Beispiel 2.4 Es sei P = (X, R) das Produktionssystem mit dem Alphabet X = {S, L, K, W, B, a, b} und der Regelmenge R, die aus den folgenden Regeln besteht. (24) S → LaK (25) aK → W bbK (26) aW → W bb (27) LW b → LaB (28) LW b → aB (29) Bb → aB (30) BK → K (31) BK → ε Die Regeln (27) und (28) zeigen, daß ein Regelsystem im allgemeinen nichtdeterministisch sein kann. In dem obigen Regelsystem gelten die folgenden beiden Ableitungen (32) S → LaK → LW bbK (33) → aBbK → aaBK → aa

(34) S → LaK → LW bbK (35) → LaBbK → LaaBK → LaaK (36) → LaW bbK → LW bbbbK → aBbbbK → aaBbbK (37) → aaaBbK → aaaaBK → aaaa, wobei jede Ableitung mit dem Wort S beginnt und das jeweils letzte Wort der Ableitung stets aus der Menge {a}∗ stammt (vgl. die n¨achste Definition). Es Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

kann also auch W¨orter geben, f¨ ur die Alternativen bei der weiteren Ableitung bestehen. Diese Alternativen k¨onnen wieder zum selben Wort f¨ uhren oder, wie hier, zu verschiedenen W¨ortern. Definition 2.5 Eine Regelgrammatik oder Typ-0-Grammatik G = (V, T, R, S) besteht aus einem Variablenalphabet V , einem Terminalzeichenalphabet T mit V ∩ T = ∅, einer endlichen Menge R von Produktionsregeln u ¨ber dem Gesamtalphabet X = V ∪T und einer Startvariablen S ∈ V . Dabei soll f¨ ur jede Regel u → v aus R in u mindestens eine Variable vorkommen. Die Menge L(G) = {x ∈ T ∗ | S →∗ x} heißt die von G erzeugte Regelsprache. Die Elemente w ∈ X ∗ mit S →∗ w nennt man auch Satzformen von G. Bemerkung 2.6 a) F¨ ur jede Regelgrammatik G ist die Sprache L(G) offensichtlich aufz¨ahlbar, da es wegen der Endlichkeit der Regelmenge nur endlich viele W¨orter geben kann, die sich aus der Startvariablen in n Schritten ableiten lassen. Diese W¨orter lassen sich f¨ ur jedes n (und damit insgesamt) effektiv aufz¨ahlen. b) Es gibt Regelgrammatiken G, f¨ ur die L(G) nicht entscheidbar ist, d. h. es ist ∗ dann X \ L(G) nicht aufz¨ahlbar. c) Die Regelgrammatik G entstehe aus der Regelgrammatik G dadurch, daß man jede Regel u → v ∈ R zu der Regel u → v ∈ R umformt. Offensichtlich ist dann L(G) die gespiegelte Sprache zu L(G). Beispiel 2.7 Es sei T ein beliebiges Alphabet, S ∈ / T und V = {S}. a) F¨ ur die Regelgrammatik G = (V, T, {S → S}, S) ist L(G) = ∅, also ∅ eine Regelsprache. b) Ist L = {w1 , . . . , wn } ⊂ T ∗ (n > 0) eine beliebige endliche Sprache u ¨ber T , so wird f¨ ur R = {(S, w1 ), . . . , (S, wn )} eine Regelgrammatik G = (V, T, R, S) mit L = L(G) definiert. Jede endliche Sprache ist daher eine Regelsprache. c) Ist R = {S → , S → aS | f¨ ur alle a ∈ T }, so wird durch G = (V, T, R, S) eine Regelgrammatik mit L(G) = T ∗ definiert. Ersetzt man die Regel S →  durch die endlich vielen Regeln S → a f¨ ur jedes a ∈ T , so sieht man, daß auch T + eine Regelsprache ist. Beispiel 2.8 a) F¨ ur V = {S, L, K, W, B}, T = {a, b} und R wie in Beispiel 2.4 n ist G = (V, T, R, S) eine Typ-0-Grammatik mit L(G) = {a(2 ) | n ≥ 1} = L2 aus Beispiel 1.19. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

b) Erweitert man die Variablenmenge um eine neue Startvariable S0 , das Terminalalphabet um ein Begrenzungszeichen # und die Regelmenge um die eine Regel S0 → #S#, dann wird mit dieser neuen Grammatik offensichtlich die Ren gelsprache L0 = {#a(2 ) # | n ∈ N} erzeugt. Man erh¨alt dieselbe Sprache aber auch durch die folgende einfachere Grammatik G = ({S, L, R}, {#, a, b}, R0 , S) mit der Regelmenge R0 = {S → #aL#,

aL → Laa, #L → #R, #L → #, Ra → aaR, R# → L#, R# → #}.

Diese neue Grammatik beschreibt exakt das Verhalten einer (nichtdeterministischen) Turing-Maschine, welche diese Sprache erzeugt: Die Variablen L und R beschreiben das Verhalten eines Lese-Schreibkopfes, der zwischen den Begrenzungszeichen # nach links bzw. rechts hin- und herwandert und dabei die jeweils schon vorhandenen Buchstaben a verdoppelt. Ein erster Buchstabe a wird durch die erste Regel zwischen die Begrenzungszeichen geschrieben. Definition 2.9 Regelgrammatiken G und G0 heißen ¨aquivalent, wenn L(G) = L(G0 ) f¨ ur die von ihnen erzeugten Regelsprachen gilt. Folgerung 2.10 Jede Typ-0-Grammatik G = (V, T, R, S) ist ¨aquivalent zu einer Typ-0-Grammatik G0 = (V 0 , T, R0 , S 0 ), bei der f¨ ur alle Regeln u0 → v 0 ∈ R0 bereits 0 0+ u ∈ V gilt. Beweisidee: Sei X 0 = {x0 | x ∈ T } eine Kopie von T , also eine zu T disjunkte gleichm¨achtige Menge. Definiere V 0 = V ∪ X 0 als neue Variablenmenge. Die Regeln aus R0 entstehen aus den Regeln u → v ∈ R, indem in u und v alle Terminalzeichen x ∈ T durch ihre Kopien x0 ∈ V 0 ersetzt werden. Schließlich werden noch alle Regeln x0 → x f¨ ur x ∈ T zu R0 hinzugef¨ ugt. Dann ist G0 eine Grammatik der gew¨ unschten Form und ersichtlich gilt L(G) = L(G0 ). Bemerkung 2.11 a) Manche Autoren nehmen wegen dieser Folgerung die Forderung u ∈ V + f¨ ur alle Regeln u → v ∈ R in die Definition der Typ-0-Grammatik mit auf. b) Die Idee in diesem Beweis, alle Terminalzeichen x durch neue “Hilfs-Variablen” x0 zu ersetzen, s¨amtliche Ableitungen zun¨achst mit diesen Hilfsvariablen durchzuf¨ uhren, und erst “am Schluß” der jeweiligen Ableitung die zus¨atzlichen abschließenden Regeln x0 → x anzuwenden, wird in vielen Beweisen angewandt, in der gewisse “Normalformen” f¨ ur die Regeln hergeleitet werden sollen. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

Definition 2.12 Eine Regelgrammatik G = (V, T, R, S) heißt beschr¨ankt oder Typ-1-Grammatik, wenn f¨ ur alle Regeln u → v aus R stets `(u) ≤ `(v) gilt. Dagegen heißt G kontextsensitiv, wenn `(u) ≤ `(v) mit einer m¨oglichen Ausnahme, n¨amlich S → ε gilt. Geh¨ort diese Regel aber zu R, so darf S in keiner rechten Seite v einer Regel vorkommen. Beispiel 2.13 a) Die Regelgrammatik aus Beispiel 2.7 a) ist eine Typ-1-Grammatik. b) Die Regelgrammatik aus Beispiel 2.7 b) ist genau dann eine Typ-1-Grammatik, wenn wi 6= ε f¨ ur alle i gilt. Sie ist aber stets kontextsensitiv. c) In Beispiel 2.7 c) ist die f¨ ur L(G) = T + gegebene Grammatik eine Typ-1Grammatik. d) Die Grammatik aus Beispiel 2.8 ist keine Typ-1-Grammatik wegen der Regeln (28), (30) und insbesondere (31). Bemerkung 2.14 a) Gilt x →∗ y f¨ ur eine Ableitung bez¨ uglich einer Typ-1Grammatik G, so folgt `(x) ≤ `(y). Insbesondere ist L(G) ε-frei, d. h. es gilt ε 6∈ L(G). Da manche Autoren diese M¨oglichkeit ε ∈ L(G) zulassen wollen, definieren sie Typ-1-Grammatiken als kontextsensitive Grammatiken im obigen Sinn. Dies macht die Inklusionen der weiter unten definierten Sprachklassen u ¨berschaubarer (vgl. Bemerkung 2.33). b) Ist G eine beschr¨ankte (oder kontexsensitive) Regelgrammatik, so ist L(G) entscheidbar, d. h. neben L(G) ist auch T ∗ \L(G) aufz¨ahlbar (vgl. Bemerkung 2.6 b)). Wegen w = ε ∈ L(G) ⇐⇒ S → ε ∈ R f¨ ur eine kontexsensitive Grammatik G, bleibt die Frage w ∈ L(G) in jedem Fall nur noch f¨ ur w 6= ε zu entscheiden. Wegen der Beschr¨anktheit von G ist w ∈ L(G) aber in h¨ochstens `(w) Schritten aus S ableitbar und alle (endlich vielen) Ableitungen dieser L¨ange sind effektiv aufz¨ahlbar. c) Es gibt Regelgrammatiken, zu denen keine ¨aquivalenten, beschr¨ankten Regelgrammatiken existieren. Definition 2.15 Eine Regelgrammatik G = (V, T, R, S) heißt kontextfrei oder Typ-2-Grammatik, wenn f¨ ur alle Regeln u → v aus R stets u ∈ V gilt. Eine kontextfreie Regelgrammatik heißt ε-frei oder 0-frei, wenn f¨ ur alle Regeln u → v aus R stets `(v) > 0 gilt, sie heißt 1-frei, wenn stets `(v) > 1 gilt.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

Beispiel 2.16 Die Grammatik aus Beispiel 2.7 a) ist eine Typ-2-Grammatik und die zugeh¨orige Sprache L(G) = ∅ ist ε-frei. Die Grammatik aus Beispiel 2.7 b) ist eine Typ-2-Grammatik. Die erzeugte Sprache L(G) ist genau dann ε-frei, wenn ur L = T + angegebene Grammatik wi 6= ε f¨ ur alle i gilt. Die in Beispiel 2.7 c) f¨ ist eine Typ-2-Grammatik und nat¨ urlich ist L ε-frei. Bemerkung 2.17 a) Wegen `(u) = 1 f¨ ur jede Regel u → v aus R ist eine kontextfreie Regelgrammatik G genau dann eine Typ-1-Grammatik, wenn in R keine Regel der Form u → ε vorkommt. Genau dann ist G und damit L(G) auch ε-frei. Ist dagegen die kontextfreie Regelgrammatik G nicht ε-frei, so kann man eine zu G ¨aquivalente Regelgrammatik G0 angeben, die kontextsensitiv ist. b) Ist G eine kontextfreie Grammatik, so ist L(G) entscheidbar, vgl. Bemerkung 2.14 b). c) Es ist entscheidbar, ob f¨ ur eine beliebige kontextfreie Grammatik G die Beziehung L(G) = ∅ gilt. d) Weitere, f¨ ur kontextfreie Grammatiken entscheidbare (und unentscheidbare) Probleme findet man in Satz 6.13. Beispiel 2.18 Die kontextfreie Regelgrammatik G = ({E, T, F }, {(, +, ∗, a, )}, R, E) sei gegeben durch das Regelsystem R = {E → E + T, E → T, T → T ∗ F, T → F, F → (E), F → a}. Die zugeh¨orige Sprache besteht aus einfachen geklammerten (arithmetischen) Ausdr¨ ucken mit den Verkn¨ upfungssymbolen + und ∗ und dem Terminalzeichen a, das eine beliebige Variable oder Konstante repr¨asentiert. Die Variablen T und F stehen hierbei f¨ ur Term und Faktor. Eine zu G ¨aquivalente Grammatik, die zu k¨ urzeren Ableitungen der W¨orter aus 0 L(G) f¨ uhrt ist G = ({E, K, O}, {(, +, ∗, a, )}, R0 , E) mit R0 = {E → (EK, E → aOE, E → a, K →)OE, K →), O → +, O → ∗}. Hierbei wird n¨amlich in jedem Ableitungsschritt genau ein Terminalzeichen erzeugt, die Ableitung eines Wortes der L¨ange ` erfolgt daher in genau ` Schritten. Dies ist bei der ersten Grammatik nicht immer der Fall, es gibt auch l¨angere Ableitungen, beispielsweise f¨ ur a + a. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

Eine weitere, ebenfalls zu G ¨aquivalente Grammatik ist G00 = ({E, T, F, A, B}, {(, +, ∗, a, )}, R00 , E) mit R00 = {E → T A, A → +T A, A → ε, T → F B, B → ∗F B, B → ε, F → (E), F → a}. In dieser Grammatik kommen keine Regeln mit Linksrekursion wie z. B. E → EK vor sondern nur solche mit Rechtsrekursion. Dies hat bei der Analyse eines Wortes w ∈ L(G) nach einer Ableitung E →∗ w (Bottom-Up-Analyse) den Vorteil, daß man nur jeweils ein Terminalzeichen des Restwortes ben¨otigt, um die benutzte Ableitungsregel zu identifizieren. Beispiel 2.19 Die kontextfreie Grammatik G = ({S, T, B}, {a, b, i, t, e}, R, S) mit der Regelmenge R = {S → iBtT eS, S → iBtS, S → a, T → iBtT eT, T → a, B → b} kann man zur Erzeugung von bedingten Ausdr¨ ucken benutzen, wenn man wie folgt interpretiert: a steht f¨ ur atomarer Ausdruck, b f¨ ur boolescher Ausdruck, i f¨ ur if, t f¨ ur then und e f¨ ur else. Definition 2.20 Es seien G = (V, T, R, S) eine Regelgrammatik, A, B, C ∈ V und x, y ∈ T ∗ . Eine Regel A → xBy aus R heißt linear. Ist hierbei x = ε so heißt sie genauer linkslinear, im Falle y = ε rechtslinear. Eine Regel A → x heißt abschließend, eine Regel der Form A → BC normal. Bemerkung 2.21 a) Jede linkslineare Regel A → Bx1 . . . xn kann mittels neu einzuf¨ uhrender Variablen Ai ∈ / V durch die n linkslinearen Regeln A → An xn , An → An−1 xn−1 , . . . , A2 → Bx1 ersetzt werden, ohne an der erzeugten Sprache etwas zu a¨ndern. Es bleiben dann nur linkslineare Regeln der Form A → Bx mit x ∈ T ∪ {ε} zu betrachten. Die analoge Aussage gilt f¨ ur rechtslineare Regeln. b) Jede abschließende Regel A → x1 . . . xn kann mittels neu einzuf¨ uhrender Variablen Ai ∈ / V durch die n − 1 linkslinearen Regeln A → An−1 xn , An−1 → An−2 xn−1 , . . . , A2 → A1 x2 und die abschließende Regel A1 → x1 ersetzt werden, ohne an der erzeugten Sprache etwas zu ¨andern. Dasselbe gilt f¨ ur analoge rechtslineare Regeln. Es bleiben dann nur abschliessende Regeln A → x mit x ∈ T ∪ {ε} und einseitig lineare Regeln der Form A → Bx bzw. A → xB mit x ∈ T ∪ {ε} zu betrachten. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

Beispiel 2.22 Die Regel in der Grammatik aus Beispiel 2.7 a) ist linkslinear und rechtslinear. Die Regeln in der Grammatik aus Beispiel 2.7 b) sind abschließend. Die Regeln in der Grammatik aus Beispiel 2.7 c) sind rechtslinear bzw. abschließend. Definition 2.23 Eine (kontextfreie) Regelgrammatik G = (V, T, R, S) heißt linear, wenn jede Regel aus R linear oder abschließend ist. Sie heißt linkslinear (rechtslinear), wenn jede Regel linkslinear (rechtslinear) oder abschließend ist. Sie heißt einseitig linear oder Typ-3-Grammatik, wenn sie linkslinear oder rechtslinear ist. Beispiel 2.24 Alle Grammatiken aus Beispiel 2.7 sind Typ-3-Grammatiken. Definition 2.25 Eine formale Sprache L ⊆ X ∗ heißt eine Typ-i-Sprache (i ∈ {0, 1, 2, 3}), wenn es eine Typ-i-Grammatik G mit L = L(G) gibt. Entsprechend definiert man kontextsensitive, lineare, linkslineare, rechtslineare und metalineare Sprachen (vgl. Definition 2.29). Beispiel 2.26 Die Sprache L7 = {an ban | n ≥ 0} ⊂ {a, b}∗ aus Beispiel 1.19 wird durch die Produktionsregeln S → b und S → aSa erzeugt. Sie ist daher linear, also insbesondere eine Typ-2-Sprache. Man kann zeigen, daß L nicht einseitig linear, also keine Typ-3-Sprache ist, da das syntaktische Monoid M (L7 ) nicht endlich ist. Es gilt n¨amlich der folgende Satz. Satz 2.27 Die Typ-3-Sprachen sind genau die regul¨aren Sprachen. Beweisidee: Sei L ⊆ X ∗ eine regul¨are Sprache, die von dem endlichen Automaten A = (Q, X, ·) mit dem Anfangszustand q0 ∈ Q und den Endzust¨anden F ⊆ Q erkannt wird. Definiert man die (offensichtlich rechtslineare) Grammatik G = (Q, X, R, q0 ) durch die Regelmenge R = {q → x(q · x) | q ∈ Q, x ∈ X} ∪ {q → ε | q ∈ F }, kann man L = L(G) nachweisen. Die Umkehrung zeigt man, indem man zu jeder rechtslinearen Grammatik G = (V, X, R, S) (unter Benutzung von Bemerkung 2.21) einen nichtdeterministischen ε-Automaten A = (Q, X, R0 , qf , qs ) (vgl. Definition 3.7) angibt, der L(G) akzeptiert. Mit den Ergebnissen des n¨achsten Abschnitts folgt hieraus die Aussage. Im einzelnen ist dabei qf ∈ / V , Q = V ∪ {qf }, q0 = S und R0 ⊆ Q × (X ∪ {ε}) × Q Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

enthalte f¨ ur jede Regel A → aB aus R das Tripel (A, a, B), f¨ ur jede Regel A → B das Tripel (A, ε, B), f¨ ur jede abschließende Regel A → a das Tripel (A, a, qf ) und schließlich f¨ ur jede Regel A → ε das Tripel (A, ε, qf ). Der Beweis f¨ ur linkslineare Grammatiken folgt durch Dualisierung, mit Aufgabe 2.43 oder durch Argumentation mit Bemerkung 2.6 c), da mit jeder regul¨aren ¨ Sprache auch die gespiegelte Sprache regul¨ar ist. Außerdem zeigen die Uberlegungen des n¨achsten Abschnitts die folgenden Aussagen. Folgerung 2.28 Zu jeder rechtslinearen Grammatik G gibt es eine ¨aquivalente linkslineare Grammatik G0 und umgekehrt. Ist G eine rechtslineare Grammatik und L(G) ε-frei, dann existiert eine Grammatik G0 , die nur Regeln der Form A → aB oder A → a mit a ∈ T enth¨alt und f¨ ur die L(G) = L(G0 ) gilt. Definition 2.29 Eine (kontextfreie) Regelgrammatik G = (V, T, R, S) heißt metalinear, wenn jede Regel aus R linear oder abschließend oder von der Form S → x mit x ∈ X ∗ ist, und wenn es keine Regel gibt, in der S auf der rechten Seite vorkommt. G heißt normal, wenn jede Regel aus R normal oder von der Form A → x mit x ∈ T ist. Beispiel 2.30 Die Sprache L9 = {an bn am bm | n, m ≥ 1} aus Beispiel 1.19 wird durch die Produktionsregeln S → AA, A → ab und A → aAb erzeugt. Sie ist daher metalinear. Man kann zeigen, daß sie nicht linear ist. Bemerkung 2.31 Es sei G = (V, T, R, S) eine beliebige lineare Grammatik. a) Ist S 0 ∈ / V , dann ist G0 = (V ∪ {S 0 }, T, R ∪ {S 0 → S}, S 0 ) eine metalineare Grammatik mit L(G0 ) = L(G). b) Jedes w ∈ X ∗ mit S →∗ w enth¨alt h¨ochstens eine Variable. Die erste abschließende Regel, die auf ein derartiges w angewandt wird, ergibt ein Wort aus L(G). Ist G metalinear, dann gibt es eine nat¨ urliche Zahl m, so daß jedes w ∈ X ∗ mit S →∗ w h¨ochstens m Variablen enth¨alt. Dabei ist m die Maximalzahl von Variablen in rechten Seiten von Regeln der Form S → w. F¨ ur viele theoretische Untersuchungen von Grammatiken ist es hilfreich, wenn die Grammatik in einer “normalisierten Form” gegeben ist. Neben Folgerung 2.28 ist der folgende Satz, der bereits auf N. Chomsky zur¨ uckgeht, ein Beispiel f¨ ur einen derartigen Normalformsatz.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

Satz 2.32 Zu jeder ε-freien Typ-2-Grammatik gibt es eine ¨aquivalente normale Grammatik. Bemerkung 2.33 Mit den Bezeichnungen K0 = Klasse aller Typ-0-Sprachen, K1 = Klasse aller Typ-1-Sprachen, KS = Klasse aller kontextsensitiven Sprachen, K20 = Klasse aller ε-freien Typ-2-Sprachen, K2 = Klasse aller Typ-2Sprachen, K3 = Klasse aller Typ-3-Sprachen, Km = Klasse aller metalinearen Sprachen, Kl = Klasse aller linearen Sprachen und Kn = Klasse aller normalen Sprachen gelten die folgenden Inklusionen K0 ⊃ K1 ⊃ K20 = Kn und K0 ⊃ KS ⊃ K2 ⊃ Km ⊃ Kl ⊃ K3 . Die folgenden S¨atze u ¨ber die (Nicht-)Abgeschlossenheit der einzelnen Sprachklassen gegen¨ uber den elementaren Operationen sind teilweise recht kompliziert zu beweisen. Im Rahmen der Vorlesung wird daher auf vollst¨andige Beweise verzichtet. Man findet sie u. a. im Buch H. Maurer, Theoretische Grundlagen der Programmiersprachen, Bibliogr. Inst., Mannheim 1969. Satz 2.34 Sind L1 und L2 Typ-i-Sprachen oder beides lineare bzw. metalineare Sprachen, so ist auch L1 ∪L2 eine Typ-i-Sprache bzw. eine lineare bzw. metalineare Sprache. Beweis: Seien Gi = (Vi , T, Ri , Si ) Grammatiken u ¨ber demselben Terminalalphabet T mit Li = L(Gi ). Es darf V1 ∩V2 = ∅ angenommen werden. Mit einem neuen Startsymbol S ∈ / V1 ∪ V2 und der Regelmenge R = R1 ∪ R2 ∪ {S → S1 , S → S2 } erzeugt G = ({S} ∪ V1 ∪ V2 , T, R, S) offensichtlich die Sprache L(G) = L1 ∪ L2 . Mit G1 und G2 ist dabei auch jeweils G von dem geforderten Typ. Satz 2.35 Die Menge der linearen Sprachen ist nicht abgeschlossen bez¨ uglich der Konkatenation, der ∗-Operation, der Durchschnittsbildung und der Komplementbildung. Die Menge der metalinearen Sprachen ist abgeschlossen bez¨ uglich der Konkatenation, aber nicht abgeschlossen bez¨ uglich der ∗-Operation, der Durchschnittsbildung und der Komplementbildung. Beweis: Bez¨ uglich der Durchschnittsbildung liefern die linearen Sprachen L1 = n n m {a b a | n, m ∈ N} und L2 = {am bn an | n, m ∈ N} das Gegenbeispiel der Sprache L = L1 ∩ L2 = {an bn an | n ∈ N}, die nicht einmal kontextfrei ist. Daher k¨onnen beide Sprachklassen auch bez¨ uglich der Komplementbildung nicht abgeschlossen sein. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

Sind Gi und S wie im Beweis von Satz 2.34 jetzt f¨ ur metalineare Sprachen Li , so seien R0 = {A → x ∈ R1 ∪ R2 | A 6= Si }, R00 = {S → x1 x2 | Si → xi ∈ Ri } und R = R0 ∪ R00 . Dann ist G = ({S} ∪ V1 ∪ V2 , T, R, S) eine metalineare Grammatik mit L(G) = L1 L2 . Die lineare Sprache L = {an bn | n ∈ N0 } liefert mit L∗ = {an1 bn1 . . . ank bnk | k, ni ∈ N0 } eine Sprache, die nicht metalinear ist, und mit LL = {an bn am bm | n, m ∈ N0 } eine Sprache die nicht linear ist. Dies sind die noch fehlenden Gegenbeispiele f¨ ur die Konkatenation und die ∗ -Operation. Satz 2.36 Sind L1 und L2 Typ-i-Sprachen, so auch L1 L2 und L∗1 (bzw. L∗1 \ {ε} f¨ ur i = 1). Satz 2.37 Sind L1 und L2 beides Typ-i-Sprachen (i = 0, 1), so auch L1 ∩ L2 . Ist L eine Typ-0-Sprache, dann ist X ∗ \ L nicht notwendigerweise eine Typ-0Sprache. Aufgabe 2.38 Geben Sie m¨oglichst einfache Regelgrammatiken G an, die L(G) f¨ ur die Sprachen L aus Aufgabe 1.64 erf¨ ullen. Aufgabe 2.39 Geben Sie eine kontextsensitive Grammatik G f¨ ur L(G) = T ∗ an. Aufgabe 2.40 Beweisen Sie eine Aussage f¨ ur lineare Regeln, die der Bemerkung 2.21 f¨ ur einseitig lineare Regeln gleicht. Aufgabe 2.41 Zeigen Sie, daß f¨ ur die von der kontextfreien Regelgrammatik G = ({S}, {a, b}, {S → a, S → b, S → aS, S → Sb}, S) erzeugte Sprache L(G) gilt: F¨ ur alle u, v ∈ {a, b}∗ ist ubav ∈ / L(G). Mit Hilfe n m dieser Aussage ist dann L(G) = L f¨ ur L = {a b | n, m ∈ N0 , n + m > 0} zu zeigen. Geben Sie weiter eine Typ-3-Grammatik G0 mit L(G0 ) = L an. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

2 REGELGRAMMATIKEN UND REGELSPRACHEN

Aufgabe 2.42 Zeigen Sie, daß f¨ ur die von der kontextfreien Regelgrammatik G = ({S}, {a, b}, {S → ε, S → bSaS, S → aSbS}, S) erzeugte Sprache L(G) gilt: L(G) = L mit L = {w ∈ {a, b}∗ | `a (w) = `b (w)}. Aufgabe 2.43 Es sei G = (V, T, R, S) eine rechtslineare Grammatik. Man bilde aus R die Regelmenge R0 wie folgt. Jede Regel der Form S → w aus R wird ur jede Regel S → wA aus R wird die Regel A → w in R0 u ¨bernaommen. F¨ in R0 aufgenommen. F¨ ur jede Regel A → w aus R wird die Regel S → Aw in R0 aufgenommen. F¨ ur jede Regel A → wB aus R wird die Regel B → Aw in R0 aufgenommen. Dann ist G0 = (V, T, R0 , S) eine linkslineare Grammatik mit L(G) = L(G0 ). Aufgabe 2.44 Gegeben ist die Grammatik G = ({S, B}, {a, b, c}, R, S) mit R = {S → ε, S → aSBc, cB → Bc, aB → ab, bB → bb}. Bestimmen Sie den Typ dieser Grammatik und zeigen Sie, daß L(G) = L f¨ ur die Sprache L = {an bn cn | n ∈ N0 } gilt.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

3 TYPEN ENDLICHER AUTOMATEN

3

Typen endlicher Automaten

Neben den in Definition 1.37 eingef¨ uhrten (deterministischen endlichen) Automaten werden in der Literatur noch andere Typen endlicher Automaten im Sinne der Definition 1.35 betrachtet. Einige davon werden in diesem Abschnitt untersucht.

Definition 3.1 Ein nichtdeterministischer endlicher Automat A = (Q, X, R, Qf , Qs ) besteht aus einer endlichen Menge Q von Zust¨anden, einem Alphabet X von ¨ Eingabezeichen, einer Ubergangsrelation R ⊆ Q × X × Q, die jedem Zustand q ∈ Q und jedem Eingabezeichen x ∈ X eine Menge {q 0 ∈ Q | (q, x, q 0 ) ∈ R} von m¨oglichen Folgezust¨anden zuordnet, einer Menge Qf ⊆ Q von Endzust¨anden und einer Menge Qs ⊆ Q von Startzust¨anden. Man bezeichnet A als deterministischen ¨ Automaten, wenn Qs = {q0 } einelementig ist und die Ubergangsrelation R eine (partielle) Funktion R : Q × X → Q definiert. Definition 3.2 Die von einem nichtdeterministischen endlichen Automaten A = (Q, X, R, Qf , Qs ) erkannte oder akzeptierte Sprache ist L(A) = {w ∈ X ∗ | w = x1 . . . xn , q0 ∈ Qs , (qi−1 , xi , qi ) ∈ R, qn ∈ Qf }, insbesondere gilt ε ∈ L(A) genau f¨ ur Qs ∩ Qf 6= ∅. Bemerkung 3.3 Ist A = (Q, X, R, Qf , Qs ) ein nichtdeterministischer Automat, so daß es Elemente (q, x) ∈ Q × X gibt, zu denen kein q 0 ∈ Q mit (q, x, q 0 ) ∈ R existiert, dann sei ∞ 6∈ Q ein neuer Zustand, Q∞ = Q ∪ {∞}, R∞ = R ∪ {(q, x, ∞) | (q, x) wie gerade beschrieben } ∪ {(∞, x, ∞) | x ∈ X} und A0 = (Q∞ , X, R∞ , Qf , Qs ). Dann ist A0 ein nichtdeterministischer endlicher Automat, f¨ ur den zu jedem Paar (q, x) ∈ Q∞ × X wenigstens ein Folgezustand existiert. Wegen ∞ ∈ / Qf gilt L(A) = L(A0 ) f¨ ur die akzeptierten Sprachen. Man darf also bei der Untersuchung der von nichtdeterministischen endlichen Auto¨ maten akzeptierten Sprachen davon ausgehen, daß die Ubergangsrelation R f¨ ur alle (q, x) ∈ Q × X mindestens einen Folgezustand liefert. Insbesondere ist dann im Falle eines deterministischen Automaten die Funktion R : Q × X → Q total definiert und es handelt sich um einen Automaten im Sinne der Definition 1.37. Dann ist L(A) genau die von A erkannte Sprache im Sinne von Definition 1.40. Man kann sogar durch Hinzunahme der Tripel (q, ε, q) f¨ ur alle q ∈ Q die Funktion R zu einer Funktion R : Q×(X ∪{ε}) → Q erweitern, ohne daß sich L(A) ¨andert. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

3 TYPEN ENDLICHER AUTOMATEN

Satz 3.4 Zu jedem nichtdeterministischen endlichen Automaten A existiert ein deterministischer endlicher Automat A0 mit L(A) = L(A0 ). Beweisidee: Ist A = (Q, X, R, Qf , Qs ) ein nichtdeterministischer endlicher Automat, so definiert man A0 = (P(Q), X, R0 , Q0f , Qs ) mit Q0f = {A ⊆ Q | A ∩ Qf 6= ∅} ⊆ P(Q) und R0 : P(Q) × X → P(Q) gem¨aß R0 (A, x) = {q 0 ∈ Q | ∃q ∈ A : (q, x, q 0 ) ∈ R}. F¨ ur alle w = x1 . . . xn ∈ X ∗ rechnet man dann w ∈ L(A) ⇐⇒ 0 w ∈ L(A ) nach. Beispiel 3.5 F¨ ur X = {0, 1} wird die Sprache L = {x1 . . . xn | xn−2 = 0} ⊆ X ∗ durch den nichtdeterministischen Automaten A = ({q0 , q1 , q2 , q3 }, X, R, {q3 }, {q0 }) ¨ mit der Ubergangsrelation R = {(q0 , 0, q0 ), (q0 , 0, q1 ), (q0 , 1, q0 ), (q1 , x, q2 ), (q2 , x, q3 ), x ∈ X} akzeptiert. Ein dazu ¨aquivalenter deterministischer Automat hat mindestens 23 = 8 Zust¨ande. Man kann dieses Beispiel verallgemeinern, indem man die Sprache L durch die Bedingung xn−k = 0 definiert. Dann ben¨otigt ein deterministischer erkennender Automat mindestens 2k+1 Zust¨ande. Bemerkung 3.6 Anders als bei deterministischen endlichen Automaten kann es nicht-isomorphe nichtdeterministische endliche Automaten mit minimaler Zustandsmenge geben, welche dieselbe Sprache erkennen. Beispielsweise erkennen die beiden Automaten Ai = ({q0 , q1 }, {0, 1}, δi , {q1 }, {q0 }) mit δ1 (q0 , 0) = {q0 , q1 }, δ1 (q0 , 1) = {q0 } und δ2 (q0 , 0) = {q1 }, δ2 (q0 , 1) = {q0 }, δ2 (q1 , 0) = {q1 }, δ2 (q1 , 1) = {q0 } dieselbe Sprache L = {x1 . . . xn | xn = 0}. Auch die folgende Definition ist als Spezialfall in der allgemeinen Definition 1.35 des endlichen Automaten enthalten. Definition 3.7 Ein nichtdeterministischer, endlicher ε-Automat A = (Q, X, R, qf , qs ) besteht aus einer endlichen Menge Q von Zust¨anden, einem Alphabet X, ¨ einer Ubergangsrelation R ⊆ Q × (X ∪ {ε}) × Q, einem Endzustand qf und einem Anfangszustand qs . Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

3 TYPEN ENDLICHER AUTOMATEN ¨ Bemerkung 3.8 a) Die Ubergangsrelation R darf jetzt auch Elemente der Form 0 ¨ (q, ε, q ) enthalten. Man kann sie als m¨ogliche spontane oder ε-Uberg¨ ange vom Zu0 + stand q in den Zustand q deuten, ohne daß ein Wort aus X “verarbeitet” wird. Bei deterministischen ε-Automaten bedeutet dies gerade, daß das Einselement ε ∈ X ∗ nicht notwendig gem¨aß q · ε = q auf den Zust¨anden q ∈ Q operieren muß. b) Es ist nicht notwendig, Mengen Qf von Endzust¨anden zu betrachten, denn man ¨ kann sie durch Hinzunahme eines neuen Zustandes qf ∈ / Q und die ε-Uberg¨ ange (q, ε, qf ) f¨ ur alle q ∈ Qf zu einem Endzustand zusammenfassen. Analog kann ¨ man mehrere Anfangszust¨ande Qs durch ε-Uberg¨ ange (qs , ε, q) aus einem neuen Anfangszustand qs ∈ / Q spontan entstehen lassen. c) Die von einem ε-Automaten akzeptierte Sprache wird wie in Definition 3.2 erkl¨art. Nur darf jetzt xi = ε f¨ ur einige oder alle i gelten. Satz 3.9 Zu jedem nichtdeterministischen, endlichen ε-Automaten A gibt es einen nichtdeterministischen, endlichen Automaten A0 mit L(A) = L(A0 ). Die bisher betrachteten Automaten waren Automaten, die nur u ¨ber eine Eingabe (und innere Zust¨ande) verf¨ ugten. Jetzt sollen auch Automaten betrachtet werden, die Zeichen ausgeben. Definition 3.10 Ein Mealy-Automat A = (I, O, Q, δ, λ) oder deterministischer endlicher Transduktor besteht aus einem Eingabealphabet I, einem Ausgabeal¨ phabet O, einer endlichen Menge Q von Zust¨anden, einer Uberf¨ uhrungsfunktion δ : Q × I → Q und einer Ausgabefunktion λ : Q × I → O. Ist die Ausgabefunktion nur von Q abh¨angig, also eine Abbildung λ : Q → O, so spricht man von einem Moore-Automaten. Ist die Abbildung λ : Q → O bijektiv, so heißt A ein Medwedew-Automat. Bemerkung 3.11 a) In einem Medwedew-Automaten erfolgt als Ausgabe bis ¨ auf die Anderung der Bezeichnung nur eine Ausgabe des jeweiligen Zustandes. Es handelt sich also dann um einen deterministischen endlichen Automaten im Sinne von Definition 1.37, der seine Zust¨ande protokolliert. Die Ausgabefunktion ist also eigentlich u ussig. ¨berfl¨ b) Transduktoren “¨ ubersetzen” gewissermaßen die W¨orter einer Eingabesprache in die W¨orter einer Ausgabesprache (vgl. die n¨achste Definition). c) Auch f¨ ur Mealy-Automaten kann man nichtdeterministisches Verhalten und auch nichtdeterministische Ausgaben betrachten, indem anstelle der Funktionen δ und λ Relationen zugelassen werden. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

3 TYPEN ENDLICHER AUTOMATEN

Definition 3.12 Es sei A = (I, O, Q, δ, λ) ein Mealy-Automat, q0 ∈ Q ein Anfangszustand und Qf ⊆ Q eine Menge von Endzust¨anden. Die Abbildungen δ ∗ : Q × I ∗ → Q und λ∗ : Q × I ∗ → O∗ seien rekursiv definiert durch (38) δ ∗ (q, ε) = q, (39) λ∗ (q, ε) = ε,

δ ∗ (q, x1 . . . xn ) = δ ∗ (δ(q, x1 ), x2 . . . xn ) λ∗ (q, x1 . . . xn ) = λ(q, x1 )λ∗ (δ(q, x1 ), x2 . . . xn ).

Dann heißt die partielle Abbildung TA : I ∗ → P(O)∗ mit TA (w) = {v ∈ O∗ | ∃q ∈ Qf : δ ∗ (q0 , w) = q, λ∗ (q0 , w) = v}. eine Automatentransformation oder GSM -Abbildung (generalized sequential maS chine). F¨ ur eine Sprache L ⊆ I ∗ setzt man TA (L) = w∈L TA (w). Beispiel 3.13 Der Mealy-Automat A = (I, O, Q, δ, λ) mit I = O = Q = {0, 1} und δ(x, y) = y sowie λ(x, y) = x gibt zun¨achst den Startzustand aus und danach, mit einem Takt Verz¨ogerung, das eingelesene Zeichen. ¨ Bei den Markierungen des folgenden Ubergangsgraphen dieses Automaten ist zu beachten, daß das jeweils erste Zeichen das eingelesene Zeichen und das jeweils zweite das ausgegebene Zeichen darstellt. (0,1) (0,0)

1

0

(1,1)

(1,0)

Beispiel 3.14 Der Mealy-Automat A = (I, O, Q, δ, λ) mit O = {0, 1}, I = O × O, Q = {S, U } und δ(S, (0, 0)) = δ(S, (0, 1)) = δ(S, (1, 0)) = S, δ(S, (1, 1)) = U, δ(U, (0, 0)) = S, δ(U, (0, 1)) = δ(U, (1, 0)) = δ(U, (1, 1)) = U sowie λ(S, (0, 0)) = λ(S, (1, 1)) = 0, λ(S, (1, 0)) = λ(S, (0, 1)) = 1, λ(U, (0, 0)) = λ(U, (1, 1)) = 1, λ(U, (1, 0)) = λ(U, (0, 1)) = 0 addiert zwei beliebig lange nat¨ urliche Zahlen in bin¨arer Darstellung, wobei die Bitfolgen von links nach rechts gelesen und verarbeitet werden. Eine Multiplikation f¨ ur beliebig lange nat¨ urliche Zahlen ist dagegen durch einen (endlichen) Mealy-Automaten nicht m¨oglich. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

3 TYPEN ENDLICHER AUTOMATEN

Satz 3.15 Ist L eine regul¨are Sprache A = (I, O, Q, δ, λ) ein Mealy-Automat, q0 ∈ Q ein Anfangszustand und Qf ⊆ Q eine Menge von Endzust¨anden, so ist auch TA (L) eine regul¨are Sprache. Bemerkung 3.16 a) Ein analoger Satz gilt f¨ ur Typ-i-Sprachen f¨ ur i = 0, 1, 2. b) Der folgende Mealy-Automat A = (I, O, Q, δ, λ) u ¨bersetzt jede beliebige Spra∗ che L ⊂ X in sich selbst. Sei X = I = O, Q = {q0 } = Qf , δ(q0 , x) = q0 und λ(q0 , x) = x f¨ ur alle x ∈ X. Dann gilt ersichtlich TA (w) = w f¨ ur alle w ∈ X ∗ und damit TA (L) = L. Der Typ der “Ausgabesprachen” von Mealy-Automaten h¨angt also vollst¨andig vom Typ der “Eingabesprachen” ab. Satz 3.17 Zu jedem Mealy-Automaten A = (I, O, Q, δ, λ) mit |I| = m und |Q| = n existiert ein ¨aquivalenter Moore-Automat mit demselben Ausgabeverhalten und n(m + 1) Zust¨anden.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

4 KELLER-AUTOMATEN UND DETERMINISTISCHE SPRACHEN

4

Keller-Automaten und deterministische Sprachen

In diesem Abschnitt werden als Verallgemeinerung der endlichen Automaten die Keller-Automaten betrachtet, die neben endlich vielen internen Zust¨anden noch u ugen. ¨ber eine besondere Art von Speicher (Kellerspeicher) verf¨ Definition 4.1 Ein (nichtdeterministischer) Keller-Automat oder Pushdown-Automat K = (Q, X, Y, δ, #, q0 ) besteht aus einer endlichen Menge Q von Zust¨anden, einem Alphabet X von Eingabezeichen, einem Alphabet Y von Kellerzeichen, einem Begrenzungszeichen ¨ # ∈ Y , einem Startzustand q0 ∈ Q und einer Ubergangsfunktion δ : Q × (X ∪ ∗ ∗ {ε}) × Y → Pf (Q × Y ), wobei Pf (Q × Y ) die Menge aller endlichen Teilmengen von Q × Y ∗ bezeichnet. Bemerkung 4.2 Die Beziehung (q 0 , z) ∈ δ(q, a, y) mit q 0 , q ∈ Q, a ∈ X, y ∈ Y , z = y1 . . . yn ∈ Y ∗ gibt an, daß der Keller-Automat K vom Zustand q mit dem Eingabezeichen a unter dem Lesekopf und dem obersten Keller-Zeichen y unter dem Lese-Schreibkopf in den Zustand q 0 u ¨bergehen kann, wobei das (oberste) Kellerzeichen y durch die Kellerzeichen y1 . . . yn ersetzt wird (und der LeseSchreibkopf jetzt auf y1 steht) und das Eingabeband um ein Feld nach links bewegt wird, d.h. unter dem Lesekopf befindet sich jetzt das auf a folgende Zeichen des Eingabewortes. Die Beziehung (q 0 , z) ∈ δ(q, ε, y) mit q 0 , q ∈ Q, a ∈ X, y ∈ Y , z ∈ Y ∗ gibt an, daß K vom Zustand q mit dem Keller-Zeichen y unter dem Lese-Schreibkopf ohne Ber¨ ucksichtigung und Bewegung des Eingabe0 bandes in den Zustand q u ¨bergehen kann, wobei y durch z ersetzt wird. Gilt δ(q, a, y) = δ(q, ε, y) = ∅ f¨ ur ein a ∈ X und befindet sich K im Zustand q, der Buchstabe a unter dem Lesekopf und der Buchstabe y unter dem LeseSchreibkopf, so h¨alt der Keller-Automat an. Definition 4.3 Es sei K = (Q, X, Y, δ, #, q0 ) ein Keller-Automat. Unter einer Situation von K versteht man ein Tripel S = (q, w, z) ∈ Q × X ∗ × Y ∗ . Man sagt eine Situation S = (q, aw, yz) f¨ uhrt unmittelbar zur Situation S 0 = (q 0 , w, z 0 z), in Zeichen S → S 0 , wenn (q 0 , z 0 ) ∈ δ(q, a, y) f¨ ur a ∈ X ∪ {ε} gilt. Weiterhin f¨ uhrt 0 ∗ 0 S zu der Situation S , in Zeichen S → S , wenn es Situationen S0 , . . . , Sn mit S = S0 , Sn = S 0 und Si−1 → Si f¨ ur i = 1, . . . , n gibt. Eine Situation der Form (q, ε, ε) heißt Endsituation.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

4 KELLER-AUTOMATEN UND DETERMINISTISCHE SPRACHEN

a

a

a

b

a

a

a

q

#

Bemerkung 4.4 Man stellt sich vor, daß im Startzustand des Keller-Automaten ein Eingabewort w ∈ X ∗ auf einem (theoretisch unbegrenzten) Eingabeband steht, wobei der Lesekopf des Keller-Automaten u ¨ber dem ersten Buchstaben von w steht. Der Kellerspeicher enth¨alt zun¨achst nur das Begrenzungszeichen #, der Lese-Schreibkopf befindet sich u ¨ber diesem Zeichen. Eine Situation gibt dann den augenblicklichen Zustand des Automaten, den noch nicht verarbeiteten Teil des Eingabewortes und das aktuelle Wort im Kellerspeicher an. Definition 4.5 Es sei K = (Q, X, Y, δ, #, q0 ) ein Keller-Automat und w ∈ X ∗ . Dann wird w von K akzeptiert, wenn es einen Zustand q ∈ Q mit (q0 , w, #) →∗ (q, ε, ε) gibt. Die Menge aller von K akzeptierten W¨orter werde mit L(K) bezeichnet. Beispiel 4.6 Der Keller-Automat K = ({q0 , q1 }, X, X ∪ {#}, δ, #, q0 ) sei durch δ(q0 , x, y) = {(q0 , xy), (q1 , xy)}, y ∈ Y, x ∈ X ∪ {ε} δ(q1 , x, x) = {(q1 , ε)}, x ∈ X δ(q1 , ε, #) = {(q1 , ε)} gegeben. Dieser Kellerautomat liest zun¨achst Zeichen f¨ ur Zeichen des Eingabewortes und schreibt die Zeichen in den Kellerspeicher, wobei er im Zustand q0 bleibt. Irgendwann wechselt er nichtdeterministisch in den Zustand q1 . Danach vergleicht er das jeweils n¨achste Zeichen des Eingabewortes mit dem obersten Zeichen des Kellerspeichers und l¨oscht im Erfolgsfall das Zeichen aus dem Kellerspeicher. (Bei Ungleichheit der Zeichen h¨alt der Kellerautomat an, ohne daß Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

4 KELLER-AUTOMATEN UND DETERMINISTISCHE SPRACHEN

eine Endsituation vorliegt!) Endet schließlich das Eingabewort und liegt im Kellerspeicher nur noch das Begrenzungszeichen, so wird dieses gel¨oscht und es liegt eine Endsituation vor. Der Kellerautomat gelangt also genau dann in eine Endsituation, wenn das Eingabewort die Form ww mit w ∈ X ∗ hat. Die Trennstelle zwischen w und w kann dabei offensichtlich nur nichtdeterministisch erkannt werden. Es ist L(K) = P AL = {ww | w ∈ X ∗ } die Sprache der Palindrome gerader L¨ange. Beispiel 4.7 Der Keller-Automat K = ({S, A, N }, {a, b}, {#}, δ, #, S) sei durch δ(S, a, #) δ(A, a, #) δ(N, a, #) δ(S, b, #) δ(A, b, #) δ(N, b, #)

= = = = = =

{(S, ##)}, {(A, ε)}, {(N, #)}, {(A, ε)}, {(N, #)}, {(N, #)}

gegeben. (Im Sinne von Definition 4.14 handelt es sich sogar um einen deterministischen Keller-Automaten.) Steht auf dem Eingabeband nur der Buchstabe b (unter dem Lesekopf), so wechselt der Keller-Automat aus dem Startzustand S in den Zustand A und der LeseSchreibkopf entfernt das einzige dort stehende Zeichen # aus dem Kellerspeicher. Da der Lesekopf auf das n¨achste Zeichen des Eingabewortes weiterwandert, findet er ε vor und der Keller-Automat befindet sich in der Endsituation (A, ε, ε). Das Wort b wird also akzeptiert. Steht auf dem Eingabeband zun¨achst das Wort an , so liest der Lesekopf diese Folge des Buchstabens a ein, der Automat bleibt im Zustand S und der Lese-Schreibkopf schreibt das Wort #n zu dem bereits dort stehenden Buchstaben # in den Kellerspeicher. Ist das Eingabewort damit beendet, so befindet sich der Keller-Automat in der Situation (S, ε, #n+1 ), das Wort an wird daher nicht akzeptiert. Folgt auf die Folge an aber ein b, so wechselt der Automat in den Zustand A und l¨oscht im Kellerspeicher das oberste Zeichen #. Da der Kellerspeicher noch nicht leer ist, ist keine Endsituation erreicht und das Wort an b wird nicht akzeptiert. Folgt ein weiterer Buchstabe b, so wechselt der Keller-Automat in den Zustand N , in dem der Kellerspeicher (bei beliebiger Eingabe) aber nicht mehr geleert werden kann, also auch keine Endsituation erreicht werden kann. Derartige W¨orter werden also nicht akzeptiert. Folgen dagegen auf das einzelne b im Eingabewort nur noch Buchstaben a, so bleibt der Keller-Automat im Zustand A und l¨oscht f¨ ur jedes a einmal das Zeichen # aus dem Kellerspeicher. Dieser wird genau dann leer, wenn nach dem Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

4 KELLER-AUTOMATEN UND DETERMINISTISCHE SPRACHEN b noch an gelesen wird. Falls damit das Eingabewort abgearbeitet ist, befindet sich der Keller-Automat in einem Endzustand und das Wort an ban wurde akzeptiert. Falls das Eingabewort noch nicht abgearbeitet ist, h¨alt der Automat an, da δ(A, w, ε) nicht definiert ist. Das Wort wird aber nicht akzeptiert. Insgesamt ergibt sich L(K) = {an ban | n ≥ 0}, also eine nicht regul¨are Sprache. Der folgende Satz zeigt, daß die Betrachtung der Zust¨ande eines Keller-Automaten eigentlich u ussig ist und durch entsprechende Kellerzeichen simuliert ¨berfl¨ werden kann. Den technisch etwas umfangreicheren Beweis findet man beispielsweise im oben bereits erw¨ahnten Buch von H. Maurer. Satz 4.8 Ist K = (Q, X, Y, δ, #, q0 ) ein Keller-Automat mit ` = |Q| Zust¨anden und k = |Y | Kellerzeichen, dann gibt es einen Keller-Automaten K0 = ({q0 }, X, Y 0 , δ 0 , #, q0 ) mit nur einem Zustand und `2 k + 1 = |Y 0 | Kellerzeichen, so daß L(K0 ) = L(K) gilt. Dieser Satz ist hilfreich beim Beweis der folgenden beiden S¨atze. Diese zeigen, daß die Keller-Automaten den Typ-2-Sprachen in derselben Weise entsprechen wie die endlichen Automaten den Typ-3-Sprachen. Diese Tatsache wurde erstmals von Chomsky bewiesen. Satz 4.9 Ist K ein Keller-Automat mit nur einem Zustand, dann ist L(K) eine Typ-2-Sprache. Beweisidee: Sei K = ({q0 }, X, Y, δ, #, q0 ) ein Keller-Automat, wobei o. B. d. A. X ∩ Y = ∅ angenommen werden darf. Definiere die Regelgrammatik G = (Y, X, R, #) durch die Regelmenge R = {y → xz | (q0 , z) ∈ δ(q0 , x, y), z ∈ Y ∗ , y ∈ Y, x ∈ X ∪ {ε}}. Dann ist G offensichtlich eine Typ-2-Grammatik. Man kann nun L(G) = L(K) zeigen. Satz 4.10 Ist L ⊆ X ∗ eine Typ-2-Sprache, dann gibt es einen Keller-Automaten K mit nur einem Zustand und Eingabealphabet X, so daß L = L(K) gilt. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

4 KELLER-AUTOMATEN UND DETERMINISTISCHE SPRACHEN

Beweisidee: Es sei G = (V, X, R, S) eine Typ-2-Grammatik. Definiere den ¨ Keller-Automaten K = ({q0 }, X, V ∪ X, δ, S, q0 ) mit der Ubergangsfunktion δ gem¨aß (1) δ(q0 , x, x) = {(q0 , ε)} f¨ ur jedes x ∈ X, und (2) δ(q0 , ε, A) = {(q0 , y) | A → y ∈ R} f¨ ur jedes A ∈ V . Mit (1) wird ein vorgelegtes Wort mit dem Inhalt des Kellerspeichers verglichen, mit (2) wird ein Wort der Sprache in den Kellerspeicher geschrieben. Dann kann man L(K) = L(G) zeigen. Beispiel 4.11 Der Keller-Automat K = ({q0 }, X, Y, δ, E, q0 ) sei gegeben durch ¨ X = {a, (, ), +, ∗}, Y = X ∪ {E, T, F } und die Ubergangsfunktion gem¨aß δ(q0 , ε, E) δ(q0 , ε, T ) δ(q0 , ε, F ) δ(q0 , x, x)

= = = =

{(q0 , E + T ), (q0 , T )}, {(q0 , T ∗ F ), (q0 , F )}, {(q0 , (E)), (q0 , a)}, {(q0 , ε)}, f¨ ur alle x ∈ X

F¨ ur das Eingabewort (a + a) ∗ a ergibt sich dann beispielsweise die (nichtdeterministische) Situationenfolge (q0 , (a + a) ∗ a, E) → → → → → → → → → → → → → →

(q0 , (a + a) ∗ a, T ) (q0 , (a + a) ∗ a, T ∗ F ) (q0 , (a + a) ∗ a, F ∗ F ) (q0 , (a + a) ∗ a, (E) ∗ F ) (q0 , a + a) ∗ a, E) ∗ F ) (q0 , a + a) ∗ a, E + T ) ∗ F ) (q0 , a + a) ∗ a, T + T ) ∗ F ) (q0 , a + a) ∗ a, F + T ) ∗ F ) (q0 , a + a) ∗ a, a + T ) ∗ F ) (q0 , +a) ∗ a, +T ) ∗ F ) (q0 , a) ∗ a, T ) ∗ F ) (q0 , a) ∗ a, F ) ∗ F ) (q0 , a) ∗ a, a) ∗ F ) (q0 , ) ∗ a, ) ∗ F )

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

4 KELLER-AUTOMATEN UND DETERMINISTISCHE SPRACHEN

→ → → →

(q0 , ∗a, ∗F ) (q0 , a, F ) (q0 , a, a) (q0 , ε, ε)

Dieser Kellerautomat akzeptiert offensichtlich genau die Sprache der einfachen arithmetischen Ausdr¨ ucke aus Beispiel 2.18. ¨ Ahnlich wie bei endlichen Automaten kann man auch bei Keller-Automaten Endzust¨ande einf¨ uhren. Dies a¨ndert aber an der Klasse der akzeptierten Sprachen nichts. Definition 4.12 Ein Endzustand-Keller-Automat oder E-Keller-Automat K = (Q, X, Y, δ, #, q0 , Qf ) besteht aus einem Keller-Automaten (Q, X, Y, δ, #, q0 ) und einer Menge Qf ⊆ Q von Endzust¨anden. Die Situationen werden wie bei Keller-Automaten definiert, aber jetzt heißt jede Situation der Form (q, ε, z) mit q ∈ Qf und z ∈ Y ∗ eine Endsituation. Ein Wort w ∈ X ∗ wird genau dann von K akzeptiert, wenn es eine Endsituation S mit (q0 , w, #) →∗ S gibt. Wiederum werde die Menge aller von K akzeptierten W¨orter mit L(K) bezeichnet. Satz 4.13 Zu jedem Keller-Automaten K gibt es einen E-Keller-Automaten K0 mit L(K) = L(K0 ) und umgekehrt. Ebenso kann man deterministische Keller-Automaten untersuchen. Definition 4.14 Ein Keller-Automat K = (Q, X, Y, δ, #, q0 ) heißt deterministisch, wenn δ die folgende Bedingung (1) erf¨ ullt. (1) F¨ ur jedes Paar (q, y) ∈ Q × Y ist δ(q, a, y) f¨ ur alle a ∈ X einelementig und es gilt δ(q, ε, y) = ∅ oder δ(q, ε, y) ist einelementig und es gilt δ(q, a, y) = ∅ f¨ ur alle a ∈ X. Ein E-Keller-Automat K = (Q, X, Y, δ, #, q0 , Qf ) heißt deterministisch, wenn δ außer (1) noch die folgende Bedingung (2) erf¨ ullt. (2) F¨ ur alle q ∈ Q und a ∈ X ∪ {ε}, f¨ ur die δ(q, a, #) 6= ∅ gilt, ist δ(q, a, #) = {(q 0 , #z)} mit q 0 ∈ Q und z ∈ Y ∗ . Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

4 KELLER-AUTOMATEN UND DETERMINISTISCHE SPRACHEN

Bemerkung 4.15 Ein deterministischer Keller-Automat hat in jeder Situation h¨ochstens eine m¨ogliche Folgesituation. Die Bedingung (2) garantiert f¨ ur EKeller-Automaten, daß sie nie anhalten, bevor das Eingabewort ganz verarbeitet ist. Satz 4.16 Ist A = (Q, X, ·) ein deterministischer Automat, der mit dem Startzustand q0 ∈ Q und den Endzust¨anden Qf ⊆ Q die Sprache L erkennt, so ist K = (Q, X, {#}, δ, #, {q0 }, Qf ) mit δ(q, a, #) = {(q·a, #)} f¨ ur alle (q, a) ∈ Q×X ein deterministischer E-Kellerautomat mit L = L(K). Folgerung 4.17 Ist L eine regul¨are Sprache, dann gibt es einen deterministischen E-Keller-Automaten mit K mit L(K) = L. Daß diese Aussage nicht schon f¨ ur deterministische Kellerautomaten gilt, zeigt der Beweis des folgenden Satzes. Satz 4.18 Ist K0 ein deterministischer E-Kellerautomat, dann gibt es nicht immer einen deterministischen Keller-Automaten K mit L(K0 ) = L(K). Beweis: Die endliche Sprache L = {a, ab} ist regul¨ar und wird folglich von einem geeigneten deterministischen E-Kellerautomaten akzeptiert. W¨are K = (Q, X, Y, δ, #, q0 ) ein deterministischer Keller-Automat mit L(K) = L, dann g¨abe es genau eine Situationenfolge (q0 , a, #) →∗ (q, ε, ε) mit q ∈ Q. Dann w¨are aber die Situationenfolge (q0 , ab, #) →∗ (q, b, ε) ebenfalls eindeutig. Da (q, b, ε) keine Endsituation f¨ ur K ist, gilt ab ∈ / L(K). Bemerkung 4.19 Das Beispiel 4.7 zeigt, daß auch umgekehrt die von einem deterministischen Keller-Automaten akzeptierte Sprache nicht regul¨ar sein muß. Definition 4.20 Eine Sprache L heißt deterministisch, wenn es einen deterministischen E-Keller-Automaten K mit L = L(K) gibt. Bemerkung 4.21 Die Klasse der deterministischen Sprachen liegt echt zwischen der Klasse der Typ-3-Sprachen und der Klasse der Typ-2-Sprachen. (Beispielsweise ist die kontextfreie Sprache {an bn cm | m, n ∈ N} ∪ {an bm cm | m, n ∈ N} nicht deterministisch, beide Teile sind dagegen deterministisch, aber nicht regul¨ar.) Man kann zeigen, daß diese Klasse abgeschlossen gegen¨ uber der Komplementbildung ist.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

5

Turing-Maschinen

In diesem Abschnitt werden die allgemeinsten zeichenverarbeitenden Maschinen behandelt, die nach dem englischen Mathematiker Alan Mathison Turing (1912 1954) benannten Turing-Maschinen. Aufbauend auf den Arbeiten von Kurt G¨odel untersuchte Turing ab 1936 mit diesem mathematischen Modell eines “Rechenautomaten” die prinzipiellen Grenzen der Berechenbarkeit. Literatur zu diesem Abschnitt: [1] Alexander Asteroth, Christel Baier, Theoretische Informatik, Pearson Studium, 2002. ISBN 3-8273-7033-7. [2] L. Balke, K. H. B¨ohling, Einf¨ uhrung in die Automatentheorie und Theorie formaler Sprachen, BI Wissenschaftsverlag, 1993. ISBN 3-411-16421-2. [3] John E. Hopcroft, Rajeev Modwani, Jeffrey D. Ullman, Einf¨ uhrung in die Automatentheorie, Formale Sprachen und Komplexit¨atstheorie, Pearson Studium, 2002. ISBN 3-8273-7020-5. ¨ [4] Christian Horn, Immo O. Kerner, Lehr- und Ubungsbuch Informatik, Band 2: Theoretische Informatik, Fachbuchverlag Leipzig, 2000. ISBN 3-446-18696-4. [5] K. R¨ udiger Reischuk, Komplexit¨atstheorie, Band I: Grundlagen, Teubner Verlag, 1999. ISBN 3-519-12275-8. [6] Ingo Wegener, Komplexit¨atstheorie, Springer Verlag, 2003. ISBN 3-540-001611. Die folgende Definition der Turing-Maschine ist dem Buch [1] entnommen. Definition 5.1 Eine (nichtdeterministische) Turing-Maschine (genauer: ein Turing-Akzeptor) T = (Q, X, Y, #, δ, q0 , Qf ) besteht aus einer endlichen Menge Q von Zust¨anden, einem Alphabet X von Eingabezeichen, einem Arbeitsalphabet Y ⊇ X mit Y ∩ Q = ∅, einem Leerzeichen # ∈ Y \ X, einem Startzustand q0 ∈ Q, einer Menge von Endzust¨anden Qf ⊆ Q ¨ und einer Ubergangsfunktion δ : Q × Y → P(Q × Y × {−1, 0, 1}). Gilt |δ(q, y)| ≤ 1 f¨ ur alle (q, y) ∈ Q × Y , so heißt T deterministisch. Ist f¨ ur eine deterministische Turing-Maschine außerdem ein Ausgabealphabet A ⊆ Y 0 = Y \ {#} ausgezeichnet, so heißt T = (Q, X, A, Y, #, δ, q0 , Qf ) Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

ein Turing-Transduktor. Unter einem Bandinhalt von T versteht man eine Abbildung inh : Z → Y , f¨ ur −1 0 die inh (Y ) endlich ist. Der effektive Bandinhalt inhef f sei dann inhef f = ε f¨ ur inh−1 (Y 0 ) = ∅ und bei inh−1 (Y 0 ) 6= ∅ wird mit m = min inh−1 (Y 0 ) und n = max inh−1 (Y 0 ) der effektive Bandinhalt gleich inhef f = y1 . . . yn−m+1 ∈ Y + mit yi = inh(m + i − 1) f¨ ur i = 1, . . . , n − m + 1 gesetzt. Bemerkung 5.2 a) Wegen q0 ∈ Q ist Q nicht leer. Die Bedingung Y ∩ Q = ∅ stellt keine Einschr¨ankung dar, da man Q andernfalls durch eine gleichm¨achtige Menge ersetzen kann. b) Da mit Q und Y auch δ stets endlich ist, gibt man δ meist in Form einer Tabelle, der Turing-Tafel, an (vgl. Beispiel 5.4). Handelt es sich bei δ um eine total definierte Funktion, also bei T um eine deterministische Turingmaschine, so besteht die Turing-Tafel offensichtlich genau aus |Q| · |Y | Zeilen. c) Die von T eigentlich zu verarbeitenden Zeichen stammen aus dem Alphabet X. Unbedingt ben¨otigt wird außerdem noch ein Trenn- oder Leerzeichen #. Weitere Zeichen aus Y dienen nur der bequemeren Notation. Da X als Alphabet mindestens ein Zeichen enth¨alt und # ∈ Y \ X gilt, besteht das Arbeitsalphabet Y jeder Turing-Maschine mindestens aus zwei Zeichen. Da man andererseits durch G¨odelisierung die freie Halbgruppe u ¨ber einem beliebigen Alphabet X auf die freie Halbgruppe u ¨ber einem einelementigen Alphabet, etwa {1}, abbilden kann, werden h¨aufig Turing-Maschinen nur u ¨ber dem Arbeitsalphabet Y = {0, 1} betrachtet, wobei die 0 die Rolle des Leerzeichens u ¨bernimmt (vgl. Beispiel 5.18 und Bemerkung 5.29). d) Ein- und Ausgabealphabet m¨ ussen im Fall des Turing-Transduktors nicht verschieden voneinander sein. e) Man stellt sich ein nach beiden Seiten unbegrenztes Band aus nebeneinanderliegenden Zellen vor, das Arbeitsband von T . Die einzelnen Zellen seien mit den ganzen Zahlen Z indiziert. Jede Zelle ist mit genau einem Zeichen aus Y beschriftet, wobei stets nur endlich viele Zellen einen Inhalt aus Y 0 = Y \ {#} besitzen. Der effektive Bandinhalt entsteht dann aus dem Bandinhalt, indem rechts und links die Teile abgeschnitten werden, die nur Leerzeichen enthalten. Weiterhin verf¨ ugt die Turing-Maschine u ber einen beweglichen Lese-Schreibkopf, der jeweils u ¨ ¨ber genau einer Zelle des Bandes positioniert ist, so daß er das dort befindliche Zeichen lesen bzw. u ¨berschreiben kann. Bei den oben definierten Turing-Maschinen handelt es sich also um eindimensionale 1-Band-1-Kopf Turing-Maschinen. Als Verallgemeinerungen werden auch Maschinen mit mehreren K¨opfen auf einem Band, mit mehreren K¨opfen auf mehreren B¨andern (vgl. Definition 5.20) und Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

mehrdimensionale Turing-Maschinen definiert. N¨ahere Einzelheiten kann man in [5] nachlesen. #

a

a

b

a

a

#

q

m

Bemerkung 5.3 Die Beziehung (q 0 , y 0 , 0) ∈ δ(q, y) mit q, q 0 ∈ Q und y, y 0 ∈ Y gibt an, daß die Turing-Maschine im Zustand q, mit dem Zeichen y unter dem Lese-Schreibkopf, ohne Bewegung des Eingabebandes den Buchstaben y durch den Buchstaben y 0 ersetzen und in den Zustand q 0 u ¨bergehen kann. Die Bezie0 0 hung (q , y , 1) ∈ δ(q, y) gibt an, daß die Turing-Maschine im Zustand q mit dem Zeichen y unter dem Lese-Schreibkopf den Buchstaben y durch den Buchstaben y 0 ersetzen, den Lese-Schreibkopf um ein Feld nach rechts verschieben und in den Zustand q 0 u ¨bergehen kann. Entsprechend erm¨oglicht (q 0 , y 0 , −1) ∈ δ(q, y) eine Linksbewegung des Lese-Schreibkopfes. Bei manchen Autoren, etwa in [3], ist eine Bewegung des Lese-Schreibkopfes sogar zwingend vorgeschrieben. Man kann aber zeigen, daß derartig definierte TuringMaschinen genau dasselbe leisten k¨onnen, wie die hier beschriebenen. Beispiel 5.4 Die folgende deterministische Turing-Maschine T = (Q, X, Y, #, δ, q0 , Qf ) bildet zu einer nat¨ urlichen Zahl in Bin¨ardarstellung n=

r−1 X

ai 2i

i=0

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

mit ai ∈ {0, 1} = X, die als Wort w = ar−1 . . . a0 u ¨ber X aufgefaßt wird, den Nachfolger n + 1. Dazu sei Y = {0, 1, #}, Q = {q0 , q1 , q2 , q3 }, Qf = {q3 } und ¨ die partiell definierte Ubergangsfunktion δ sei durch die folgende Turing-Tafel gegeben. Dabei ist jede Zeile ein Element aus Q × Y × Q × Y × {−1, 0, 1}. Die letzten drei Zeilen deuten an, daß δ(q3 , y) undefiniert ist. Man kann δ zu einer total definierten Funktion machen, indem man in den letzten drei Zeilen q3 , y, q3 , y, 0 f¨ ur y = 0, 1, # setzt. Bei vielen Autoren werden diese Zeilen einfach fortgelassen. q0 , q0 , q0 , q1 , q1 , q1 , q2 , q2 , q2 , q3 , q3 , q3 ,

0, 1, #, 1, 0, #, 1, 0, #, 0, 1, #,

q0 , q0 , q1 , q1 , q2 , q3 , q2 , q2 , q3 , -, -, -,

0, 1, #, 0, 1, 1, 1, 0, #, -, -, -,

1; 1; -1; -1; -1; 0; -1; -1; 1; -; -; -;

In den ersten drei Zeilen wird festgelegt, daß T ans rechte Ende der Eingabe l¨auft, ohne die Zeichen zu ver¨andern. Anschließend steht der Lese-Schreibkopf auf a0 und T befindet sich im Zustand q1 . In der vierten Zeile wandelt T von rechts aus aufeinanderfolgende Einsen in Nullen um, bis sie auf eine 0 trifft, die sie durch 1 ersetzt und in den Zustand q2 u ¨bergeht, oder auf #, was sie ebenfalls durch eine 1 ersetzt und in den Zustand q3 u ¨bergeht. Im letzten Fall hatte n die Bin¨ardarstellung 1 . . . 1 und die Addition von 1 ist beendet. Ansonsten l¨auft T im Zustand q2 ans linke Ende des Eingabewortes und bleibt auf der f¨ uhrenden Bin¨arziffer stehen. Diese einfache Turing-Maschine zur Berechnung der Nachfolgerfunktion hat noch zwei kleine Sch¨onheitsfehler: Sie verarbeitet die leere Eingabe nicht korrekt und akzeptiert auch Eingaben mit “f¨ uhrenden Nullen”. Dies wird im folgenden Beispiel behoben. Beispiel 5.5 Die folgende deterministische Turing-Maschine Tid = ({q00 , q000 , q0 }, {0, 1}, {0, 1, #}, #, δid , q00 , {q0 }) pr¨ uft ein Eingabewort w aus X ∗ daraufhin, ob es sich um eine nat¨ urliche Zahl in Bin¨ardarstellung handelt, also insbesondere ob keine f¨ uhrenden Nullen auftreten Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

und ob w 6= ε gilt. Die Bezeichnung der Zust¨ande ist so gew¨ahlt, daß man diese und die Turing-Maschine aus Beispiel 5.4 problemlos hintereinanderschalten ¨ kann. Die Ubergangsfunktion δid ist durch folgende Turing-Tafel gegeben. q00 , q00 , q00 , q000 , q000 , q000 ,

0, q000 , 1, q0 , #, -, 0, -, 1, -, #, q0 ,

0, 1, -, -, -, #,

1; 0; -; -; -; -1;

falls falls falls falls falls falls

f¨ uhrende Null, also evtl. w = 0 keine f¨ uhrende Null, dann akzeptiert w = ε, dann verworfen mehrere f¨ uhrende Nullen, dann verworfen f¨ uhrende Null, aber w 6= 0, dann verworfen w = 0, dann akzeptiert

Definition 5.6 Unter einer Situation oder Konfiguration einer Turing-Maschine T = (Q, X, Y, #, δ, q0 , Qf ) versteht man ein Element S ∈ ST = Q × Y Z × Z. Sie beschreibt den aktuellen Zustand von T , den Innhalt des Arbeitsbandes und die aktuelle Position des LeseSchreibkopfes. Die Anfangssituation von T bei Eingabe von w = x1 . . . xn ∈ X ∗ ist dann ST0 (w) = (q0 , inh0 , 0) mit inh0 (i) = xi+1 f¨ ur i = 0, . . . , n−1 und inh0 (i) = # sonst. Man sagt, S = (q, inh, j) f¨ uhrt unmittelbar zu S 0 = (q 0 , inh0 , j 0 ), in Zeichen S → S 0 , wenn die folgenden Bedingungen erf¨ ullt sind (1) es gibt ein (q 0 , y 0 , m) ∈ δ(q, inh(j)), (2) j 0 = j + m, (3) inh0 (i) = inh(i) f¨ ur alle i 6= j und inh0 (j) = y 0 . Man sagt, eine Situation S f¨ uhrt zu einer Situation S 0 , in Zeichen S →∗ S 0 , wenn es Situationen S0 , . . . , Sn (n ≥ 0) gibt mit S = S0 , Sn = S 0 und Si−1 → Si f¨ ur i = 1, . . . , n. Eine Situation S = (q, inh, j) heißt Endsituation, wenn es keine Situation S 0 mit S → S 0 gibt. F¨ ur q ∈ Qf heißt dann S akzeptierend, sonst verwerfend. Bemerkung 5.7 Bei vielen Autoren wird in der Definition der Situation der Bandinhalt durch den effektiven Bandinhalt ersetzt. F¨ ur inhef f = y1 . . . yn notiert man dann die Situation als αqβ = y1 . . . yi−1 qyi . . . yn , wenn sich T im Zustand q befindet und der Lese-Schreibkopf u ¨ber der Zelle mit dem Buchstaben yi . Man muß hier allerdings Sonderf¨alle unterscheiden, wenn der Lese-Schreibkopf hinter dem letzten Buchstaben des effektiven Bandinhaltes steht, oder das Arbeitsband nur das leere Wort enth¨alt.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

Bei der hier gegebenen Definition der Endsituation ist δ(q, inh(j)) = ∅ notwendig. Insbesondere bei deterministischen Turing-Maschinen muß es sich bei den ¨ Ubergangsfunktionen also um partielle Funktionen auf Q × Y handeln. Manche Autoren setzen sogar δ(q, y) = ∅ f¨ ur alle q ∈ Qf und alle y ∈ Y voraus. Bei anderen Autoren wird explizit gefordert, daß die Turing-Maschine anh¨alt, ¨ sobald sie einen Endzustand erreicht, auch wenn die Ubergangsfunktion noch definiert sein sollte. Bei diesem Vorgehen ist es m¨oglich, δ f¨ ur jede deterministische Turing-Maschine T als total definierte Funktion vorauszusetzen, indem man δ(q, a) = {(q, a, 0)} definiert, falls δ(q, a) = ∅ f¨ ur ein (q, a) ∈ Q × Y gelten sollte (vgl. hierzu [4]). Hierdurch wird das Verhalten der Turing-Maschine dann n¨amlich nicht ver¨andert. Schließlich gibt es auch Definitionen, bei denen eine Teilmenge Qa ⊆ Qf von akzeptierenden Endzust¨anden ausgezeichnet wird, die restlichen Endzust¨ande sind dann verwerfend. In [6] werden die Haltezust¨ande Qf ⊆ Q dadurch definiert, daß δ(q, y) = (q, y, 0) f¨ ur alle y ∈ Y und q ∈ Qf gilt, w¨ahrend f¨ ur q ∈ Q \ Qf und alle y ∈ Y stets δ(q, y) 6= (q, y, 0) gilt. Hier ist δ total definierte Funktion. Die Menge Qf wird dann weiter in zwei disjunkte Teilmenge Q+ der akzeptierenden und Q− der verwerfenden Haltezust¨ande zerlegt. Definition 5.8 Es sei T = (Q, X, Y, #, δ, q0 , Qf ) eine Turing-Maschine. Eine Berechnung oder ein Lauf von T f¨ ur ein Eingabewort w ∈ X ∗ ist eine maximale Folge von Situationen q0 w → α1 q1 β1 → α2 q2 β2 → . . . Dabei sind genau drei F¨alle m¨oglich 1) Die Berechnung ist unendlich. 2) Die Berechnung ist endlich, aber verwerfend, d. h. sie endet mit αn qn βn f¨ ur qn 6∈ Qf und entweder βn = ε sowie δ(qn , #) undefiniert, oder βn = b . . . und δ(qn , b) undefiniert f¨ ur ein b ∈ Y \ {#}. 3) Die Berechnung ist endlich und akzeptierend, d. h. sie endet mit αn qn βn f¨ ur qn ∈ Qf . Mit L(T ) werde die Menge aller Eingabew¨orter bezeichnet, zu denen eine akzeptierende Berechnung von T existiert. Beispiel 5.9 a) Die Turing-Maschine aus Beispiel 5.4 f¨ uhrt f¨ ur w = 101 die folgende akzeptierende Berechnung aus (die beiden begrenzenden Leerzeichen sind nur der Deutlichkeit halber mit angegeben): #q0 101# → #1q0 01# → #10q0 1# → #101q0 # → #10q1 1# Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

→ #1q1 00# → #q2 110# → q2 #110# → #q3 110#. F¨ ur w = ε f¨ uhrt sie ebenfalls die (sicherlich nicht beabsichtigte) akzeptierende Berechnung aus: #q0 # → q1 ## → q3 1#. Schaltet man nun aber die Turing-Maschine aus Beispiel 5.5 davor, so ergibt sich / Qf = {q3 }. Dagegen f¨ ur w = ε jetzt die verwerfende Berechnung #q00 #, da q00 ∈ wird f¨ ur w = 0 akzeptierend berechnet #q00 0# → #0q000 # → #q0 0# → #0q0 # → #q1 0# → q2 #1# → #q3 1#. Satz 5.10 Zu jedem nichtdeterministischen Turing-Akzeptor T gibt es einen deterministischen Turing-Akzeptor T 0 mit L(T ) = L(T 0 ). Beweisidee: Die zur akzeptierenden Berechnung von w ∈ L(T ) von T “parallel” durchlaufenen Konfigurationen werden von T 0 per Breitensuche “seriell” durchlaufen. Dabei garantiert die Breitensuche (im Unterschied zur Tiefensuche), daß die akzeptierende Berechnung auch gefunden wird. Der folgende Satz zeigt den wesentlichen Zusammenhang zwischen Turing-Maschinen und formalen Sprachen. Die Beweise der einzelnen Aussagen sind teilweise recht umfangreich. Man findet sie in dem weiter oben zitierten Buch von Maurer.

Satz 5.11 Ist T = (Q, X, Y, #, δ, q0 , Qf ) eine Turing-Maschine, dann ist L(T ) eine Typ-0-Sprache. Umgekehrt gibt es zu jeder Typ-0-Sprache L eine TuringMaschine T mit L = L(T ). Beispiel 5.12 Die Turing-Maschine T = ({q0 , q1 , q2 , q3 , q4 }, {0, 1}, {0, 1, x, y, #}, #, δ, q0 , {q4 }) mit der Turing-Tafel q0 , 0, q0 , y, q1 , 0, q1 , 1, q1 , y, q2 , 0, q2 , x, q2 , y, q3 , y, q3 , #,

q1 , x, 1; die erste 0 wird in ein x verwandelt q3 , y, 1; es sind keine Nullen mehr vorhanden q1 , 0, 1; weitere Nullen werden u ¨bergangen q2 , y, -1; die erste 1 wird in ein y verwandelt q1 , y, 1; alle y werden u ¨bergangen q2 , 0, -1; das erste x von rechts wird gesucht q0 , x, 1; eine weitere 0 wird gesucht q2 , y, -1; das erste x von rechts wird gesucht q3 , y, 1; alle y werden u ¨bergangen q4 , #, 1; keine 1 mehr gefunden, Wort wird akzeptiert

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN akzeptiert die Sprache L(T ) = {0n 1n | n ∈ N}. Sind n¨amlich weniger Nullen als Einsen vorhanden, liest T im Zustand q3 eine 1, sind mehr Nullen als Einsen vorhanden, liest T im Zustand q1 ein #. In beiden F¨allen ist δ undefiniert, aber kein Endzustand erreicht. Definition 5.13 Ist T = (Q, X, A, Y, #, δ, q0 , Qf ) ein Turing-Transduktor, so wird durch T die folgende partielle Funktion f (T ) : X ∗ → A∗ definiert. Falls das Eingabewort w ∈ X ∗ keine akzeptierende Berechnung durch T besitzt, so ist f (T )(w) undefiniert. Andernfalls sei u der effektive Bandinhalt am Ende der (eindeutig bestimmten) akzeptierenden Berechnung zu w. Ersetze in u alle Buchstaben aus Y \ A durch ε. Das resultierende Teilwort u0 von u ist dann f (T )(w). Beispiel 5.14 Die Hintereinanderschaltung der Turing-Maschinen aus den Beispielen 5.4 und 5.5 ergibt einen Turing-Transduktor, der die Nachfolgerfunktion n 7→ n + 1 auf der Menge aller Bin¨arzahlen u ¨ber {0, 1} berechnet. Beispiel 5.15 Die deterministische Turing-Maschine T = ({q0 , . . . , q6 }, {0, 1}, {0, 1, #}, 0, δ, q0 , {q6 }) mit der Turing-Tafel q0 , q0 , q1 , q1 , q2 , q2 , q2 , q3 , q3 , q3 , q4 , q4 , q4 , q5 , q5 , q5 ,

1, 0, 1, 0, 1, 0, #, 1, 0, #, 1, 0, #, 1, 0, #,

q1 , q5 , q1 , q2 , q3 , q2 , q4 , q3 , q3 , q0 , q4 , q4 , q6 , q5 , q5 , q6 ,

#, #, 1, 0, 0, 0, #, 1, 0, #, 1, #, 1, #, #, #,

1; 1; 1; 1; -1; 1; -1; -1; -1; 1; -1; -1; 1; 1; 1; 1;

erste 1 von links wird gel¨oscht falls links keine 1 mehr vorhanden die restlichen Einsen links u ¨bergehen die 0 zwischen beiden Zahlen wird gefunden erste Eins rechts wird in 0 verwandelt Nullen werden¨ ubergangen rechter Summand abgearbeitet linkes Ende wird gesucht linkes Ende wird gesucht linkes Ende gefunden, n¨achste Ziffer Einsen des Ergebnisses werden u ¨bergangen Nullen werden in Leerzeichen verwandelt zuviel gel¨oschte 1 wird verwandelt, dann Stop Ergebnis muss Null sein, alles l¨oschen Ergebnis muss Null sein, alles l¨oschen Ergebnis ist Null, also Stop

berechnet f¨ ur nat¨ urliche Zahlen m und n in Un¨ardarstellung, also als Folgen von Einsen, durch eine 0 als Zwischenraum getrennt, die Funktion f : N2 → N mit f (m, n) = max(m − n, 0), also die Subtraktion auf den nat¨ urlichen Zahlen. Das Leerzeichen # wird auch zur Markierung der jeweils bearbeiteten Eins benutzt. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

Definition 5.16 Eine Turing-Maschine T = (Q, X, Y, #, δ, q0 , Qf ) besitzt ein linksseitig beschr¨anktes Band, wenn ein Zeichen $ ∈ Y \ (X ∪ {#}) existiert, so daß f¨ ur alle Zust¨ande q ∈ Q die beiden folgenden Bedingungen gelten. (1) δ(q, $) ⊆ {(q 0 , $, 1), (q 0 , $, 0) | q 0 ∈ Q} und (2) δ(q, y) ∩ {(q 0 , $, m) | q 0 ∈ Q, m ∈ {−1, 0, 1}} = ∅ f¨ ur alle y ∈ Y \ {$}. F¨ ur jedes Eingabewort w = x1 . . . xn ∈ X ∗ ist dann die Anfangskonfiguration von T gleich $q0 w mit inh(−1) = $ und inh(i) = xi+1 f¨ ur i = 0, . . . , n − 1 sowie inh(i) = # sonst. Bemerkung 5.17 Wegen (1) steht das Begrenzungszeichen $ stets in Bandzelle -1 und darf durch den Lese-Schreibkopf niemals nach links u ¨berschritten werden. Wegen (2) darf $ auch in keine andere Bandzelle geschrieben werden. Beispiel 5.18 a) Die deterministische Turing-Maschine T = ({q0 , . . . , q7 }, {1}, {1, 0}, 0, δ, q0 , {q7 }) ¨ mit der Ubergangsfunktion q0 , 0, q0 , q0 , 1, q1 , q1 , 0, q2 , q1 , 1, q1 , q2 , 0, q3 , q2 , 1, q2 , q3 , 0, q4 , q3 , 1, q3 , q4 , 0, q7 , q4 , 1, q5 , q5 , 0, q6 , q5 , 1, q5 , q6 , 0, -, q6 , 1, q1 , q7 , 0, -, q7 , 1, q7 ,

0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, -, 0, 0, 1,

1; 1; 1; 1; -1; 1; -1; -1; -1; -1; 1; -1; -; 1; -; -1;

kopiert eine Folge von Einsen auf einem sonst mit Nullen (als Leerzeichen) beschriebenen Arbeitsband nach rechts mit einer Bandzelle Zwischenraum, in der eine Null stehen bleibt. Dabei l¨auft sie nach links niemals u ¨ber die Null hinaus,

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

die unmittelbar links von den eingegebenen Einsen steht. Es handelt sich also de facto um eine Turing-Maschine mit linksseitig beschr¨anktem Band. b) Erweitert man die in a) angegebene Turing-Maschine um Zust¨ande q8 , . . . , q13 , wobei q8 jetzt Startzustand und q13 einziger neuer Endzustand ist, und ¨andert bzw. erg¨anzt die Turing-Tafel gem¨aß q7 , q7 , q8 , q8 , q9 ,

0, q10 , 1, q7 , 0, q8 , 1, q9 , 0, q0 ,

q9 , q10 , q10 , q11 , q11 , q12 , q12 , q13 , q13 ,

1, 0, 1, 0, 1, 0, 1, 0, 1,

0, -1; 1, -1; 0, 1; 0, 1; 0, 1;

Ende des Kopierprogramms Linksverschiebung zum linken Ende von n das linke Ende von m wird gesucht das linke Ende von m wird mit einer 0 markiert die 0 zwischen m und n wird u ¨bersprungen, n wird kopiert q9 , 1, 1; das rechte Ende von m wird gesucht q13 , 1, -1; Markierung wird am Ende von m entdeckt q11 , 1, -1; Linksverschiebung von der 0 zwischen m und n q12 , 1, 1; Beginn der Rechtsverschiebung der Markierung in m q11 , 1, 1; Linksverschiebung durch m bis zur Markierung -, -, -; kann niemals eintreten q9 , 0, 1; Ende der Rechtsverschiebung der Markierung in m -, 0, -; Berechnung beendet q13 , 1, -1; Linksverschiebung zum linken Ende von m

so erh¨alt man eine deterministische Turing-Maschine f¨ ur die Multiplikation nat¨ urlicher Zahlen m und n, die als m und n Einsen, getrennt durch eine einzelne Null auf einem ansonsten mit Nullen gef¨ ullten Arbeitsband stehen. Auch bei dieser Turing-Maschine ist das Arbeitsband linksseitig beschr¨ankt. Satz 5.19 Zu jeder Turingmaschine T gibt es eine Turingmaschine T 0 mit linksseitig beschr¨anktem Band, die T simuliert, d. h. als Akzeptoren akzeptieren beide Turing-Maschinen dieselben Sprachen und als Transduktoren erzeugen beide Turing-Maschinen dieselben Ausgaben. Beweisidee: Das Arbeitsband . . . , −2, −1, 0, 1, 2, . . . von T wird bei 0 zerlegt, “verzahnt” und nach links durch $ beschr¨ankt gem¨aß $, 0, −1, 1, −2, 2, . . .. Dies ist jetzt der “rechte” Teil des Arbeitsbandes von T 0 . Als Zust¨ande erh¨alt T 0 f¨ ur jeden Zustand q ∈ Q zwei Zust¨ande ql , qr , die unterscheiden, ob T sich gerade in der linken oder der rechten Bandh¨alfte befindet. F¨ ur jede Bewegung des Kopfes von T um eine Zelle bewegt sich der Kopf von T 0 um 2 Zellen (Normalfall) oder um 3 Zellen (wenn T die Zelle 0 u ¨berschreitet). Die Zeit- und Platzkomplexit¨aten 0 von T und T stimmen daher u ¨berein.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

Definition 5.20 Eine (nichtdeterministische) k-Band-Turing-Maschine f¨ ur k ∈ N

T = (Q, X, Y, #, δ, q0 , Qf ) ¨ ist gegeben durch dieselben Gr¨oßen wie eine Turing-Maschine, lediglich die Uberk gangsfunktion ist jetzt eine Abbildung δ : Q × Y → P(Q × (Y × {−1, 0, 1})k ). Die Konfigurationen von T schreibt man dann in der Form β1 α1  ..   ..   . q . . αk βk 

 



Beispiel 5.21 Zur Berechnung der partiellen Funktion f : {0, 1}∗ → {0, 1}∗ mit f (0n 1n ) = 0n f¨ ur n ≥ 1 definiere die deterministische 2-Band-Turing-Maschine T = ({q0 , q1 , q2 }, {0, 1}, {0, 1, #}, #, δ, q0 , {q2 }), f¨ ur die Band 1 ein reines Eingabeband ist, auf dem nur ein Lesekopf arbeitet, und Band 2 ein reines Ausgabeband, auf dem nur ein Schreibkopf arbeitet. Die ¨ Ubergangsfunktion sei durch folgende Turing-Tafel beschrieben: q0 , q0 , q1 , q1 ,

0, 1, 1, #,

# # 0, #,

q0 , q1 , q1 , q2 ,

0, 1, 0, 1; 1, 0, #, -1; 1, 1, 0, -1; #, 0, #, 1;

F¨ ur w = 01 ergibt sich die folgende akzeptierende Berechnung 

q0

01 ##

→





→

0 1 q0 0 #

 



01 # q1 # #0# 







→

→





0 1 q1 # 0# 





01 # q2 . # 0# 





F¨ ur w = 011 ergibt sich die folgende verwerfende Berechnung 

q0

011 ##



→

0 11 q 0 0 #

 





→



0 11 q # 1 0# 





→



01 1 q . # 1 #0# 





Satz 5.22 Jede k-Band-Turing-Maschine kann durch eine Einband-Turing-Maschine simuliert werden (vgl. [1]).

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

Turingsche These: Jeder Algorithmus l¨aßt sich durch eine Turing-Maschine realisieren. Der Begriff der durch Algorithmen berechenbaren Funktionen wurde im Laufe der Zeit auf verschiedene Weisen formalisiert, z. B. durch Markov (MarkovAlgorithmen), durch Kleene (µ-rekursive Funktionen), durch Church (λ-Kalk¨ ul). Alle Definitionen haben sich als gleichwertig zur Berechenbarkeit mittels TuringMaschinen erwiesen. Daher wird die Turingsche These heute allgemein akzeptiert.

Definition 5.23 Sei X = {b0 , . . . , bq−1 } ein Alphabet, X 0 = {0, 1} und m = min{i + 1 | q − 1 ≤ 2i }. Definiere β : X ∗ → X 0∗ durch β(ε) = ε, β(br ) = r in m-stelliger Bin¨ardarstellung und β(x1 . . . xn ) = β(x1 ) . . . β(xn ). Dann heißt β bin¨are Verschl¨ usselung von X. Ist X 00 = {1} und p1 = 2, p2 = 3, . . . die Folge der Primzahlen sowie e(x1 . . . xn ) = pj11 +1 · · · pjnn +1 mit xi = bji , dann heißt die durch ϕ(x1 . . . xn ) = 1e(x1 ...xn ) definierte Funktion ϕ : X ∗ → X 00∗ eine G¨odelisierung von X. Beispiel 5.24 F¨ ur X = {a, b, c} ergibt sich q = 3, also m = 2, und daher β(a) = 00, β(b) = 01 und β(c) = 10 als bin¨are Verschl¨ usselung. F¨ ur die G¨odelisierung ergibt sich e(a) = 21 , e(b) = 22 , e(c) = 23 und damit ϕ(a) = 11, ϕ(b) = 1111, ϕ(c) = 11111111 und z. B. e(aa) = 21 · 31 = 6, also ϕ(aa) = 111111. Definition 5.25 Sind T = (Q, X, Y, #, δ, q0 , Qf ) und T 0 = (Q0 , X 0 , Y 0 , #, δ 0 , q00 , Q0f ) Turing-Maschinen mit X 0 = {0, 1} und ist β die bin¨are Verschl¨ usselung von X, dann heißt T 0 {0, 1}-gleichwertig mit T , wenn q0 w →∗ yq mit q ∈ Qf genau dann gilt, wenn q00 β(w) →∗ β(y)q 0 mit q 0 ∈ Q0f gilt. Satz 5.26 Zu jeder Turing-Maschine T gibt es eine {0, 1}-gleichwertige TuringMaschine T 0 . Bemerkung 5.27 Mit Hilfe dieses Satzes kann man f¨ ur jede Turing-Maschine T mit linksseitig beschr¨anktem Rand die sogenannte Standardbeschreibung ST B(T ) einf¨ uhren, was technisch etwas aufwendig ist und hier daher unterbleibt. Dann Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

5 TURING-MASCHINEN

kann man den folgenden Satz beweisen, der zeigt, daß es universelle TuringMaschinen gibt, die die Berechnungen jeder anderen Turing-Maschine (in Standardbeschreibung) nachvollziehen. Zusammen mit der Turingschen These bedeutet dies, daß keine noch so komplizierte Rechenanlage mehr ausf¨ uhren kann als eine derartige Turing-Maschine. Satz 5.28 Es gibt Turing-Maschinen T = (Q, X, Y, #, δ, q0 , Qf ), genannt universelle Turing-Maschinen, mit der folgenden Eigenschaft: Ist T 0 = (Q0 , X 0 , #, δ 0 , q00 , Q0f ) eine beliebige Turing-Maschine mit linksseitig beschr¨anktem Rand, so gilt q00 w →∗ yq 0 mit x, y ∈ X 0∗ und q 0 ∈ Q0f genau dann, wenn q0 ST B(T 0 )β(w) →∗ ST B(T 0 )β(y)q mit q ∈ Qf . Bemerkung 5.29 Claude Shannon konstruierte 1956 eine universelle TuringMaschine mit nur 2 Zust¨anden und zeigte, daß es keine universelle Turing-Maschine mit nur einem Zustand geben kann. Im selben Artikel gab er eine universelle Turing-Maschine mit nur 2 Eingabezeichen an. Man nennt eine Turing-Maschine linear beschr¨ankt, wenn der Lese-Schreibkopf auf dem Arbeitsband niemals den Bereich verl¨aßt, auf dem das jeweilige Eingabewort steht. Dann gilt folgende Aussage. Ist T linear beschr¨ankt, dann ist L(T ) \ {ε} eine Typ-1-Sprache. Umgekehrt gibt es zu jeder Typ-1-Sprache L eine nichtdeterministische Turing-Maschine T mit L = L(T ). Es ist ein noch offenes Problem, ob diese Aussage auch f¨ ur deterministische Turing-Maschinen richtig bleibt.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

6 PUMPING-LEMMA UND FOLGERUNGEN

6

Pumping-Lemma und Folgerungen

Die im folgenden bewiesenen Aussagen geben Hilfsmittel an die Hand, um von verschiedenen Sprachen zeigen zu k¨onnen, daß sie nicht zu einer bestimmten Sprachklasse geh¨oren. Lemma 6.1 Pumping-Lemma fu are Sprachen Es sei A = (Q, X, ·) ¨ r regul¨ ein endlicher Automat, der mit dem Anfangszustand q0 ∈ Q und den Endzust¨anden F ⊆ Q die regul¨are Sprache L erkennt. F¨ ur jedes Wort w ∈ L mit `(w) ≥ n = |Q| existieren W¨orter x, y, z ∈ X ∗ , so daß gelten (40) w = xyz (41) 0 < `(y) ≤ n ν (42) xy z ∈ L f¨ ur jedes ν ∈ N0 . Insbesonder gilt xz ∈ L. Beweis: Sei w = x1 . . . xm ∈ L mit m ≥ |Q| und q0 , . . . , qm ∈ Q mit qi−1 · xi = qi f¨ ur i = 1, . . . , m und qm ∈ F . Dann gibt es k < ` in P = {0, . . . , m} mit qk = q` . W¨ahle solche k und `, deren Differenz ` − k minimal wird, also insbesondere ` − k ≤ n erf¨ ullt. Setze x = x1 . . . xk , y = xk+1 . . . x` und z = x`+1 . . . xm . Dann gilt q0 ·x = qk , qk ·y = q` = qk und folglich qk ·y ν = qk f¨ ur alle ν ∈ N0 und schließlich ν qk · z = qm ∈ F . Es folgt xy z ∈ L. Weiterhin gilt `(xz) = k + (m − `) < m. Bemerkung 6.2 a) Der nichtleere Teil y von w ∈ L kann also innerhalb von L beliebig “aufgepumpt” werden. b) Falls es also ein Wort w ∈ L mit `(w) ≥ |Q| gibt, so folgt |L| = ∞. Ist daher L eine endliche (regul¨are) Sprache mit k = max{`(w) | w ∈ L}, dann hat jeder Automat, der L erkennt mindestens k + 1 Zust¨ande. Im Fall |L| = 1 reicht diese Anzahl an Zust¨anden auch aus. c) Andererseits existiert zu jedem Wort w ∈ L mit m = `(w) ≥ |Q| ein Wort w0 ∈ L mit `(w0 ) < `(w), also letztlich ein Wort einer L¨ange kleiner als |Q|. Hieraus ergibt sich das folgende Kriterium f¨ ur die Entscheidbarkeit von L = ∅ f¨ ur eine regul¨are Sprache (vgl. Bemerkung 1.24 c)). Folgerung 6.3 Es sei A = (Q, X, ·) ein endlicher Automat, der mit dem Anfangszustand q0 ∈ Q und den Endzust¨anden F ⊆ Q die regul¨are Sprache L erkennt. Dann gilt L = ∅ ⇐⇒ ∀w0 ∈ X ∗ , `(w0 ) < |Q| : w0 ∈ / L. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

6 PUMPING-LEMMA UND FOLGERUNGEN Definition 6.4 Es sei w ∈ X ∗ . Eine Folge Φ = (w1 , . . . , wm ) mit wi ∈ X ∗ und w = w1 . . . wm heißt Zerlegung von w. Eine Position von w ist eine Zahl i ∈ {1, . . . , `(w)}. Eine Position i liegt bez¨ uglich Φ im k-ten Teilwort von w, falls gilt `(w1 . . . wk−1 ) < i ≤ `(w1 . . . wk ). Lemma 6.5 Ogden-Lemma fu are Sprachen Es sei A = (Q, X, ·) ein ¨ r regul¨ endlicher Automat, der mit dem Anfangszustand q0 ∈ Q und den Endzust¨anden F ⊆ Q die regul¨are Sprache L erkennt. F¨ ur jedes Wort w ∈ L mit `(w) ≥ |Q| und jede Menge P von Positionen in w mit |P | ≥ |Q| gibt es eine Zerlegung Φ = (x, y, z) von w, so daß gilt 1. xy ν z ∈ L f¨ ur alle ν ∈ N0 , 2. Die Anzahl der Positionen aus P , welche bez¨ uglich Φ im zweiten Teilwort liegen, ist positiv und durch |Q| nach oben beschr¨ankt. Bemerkung 6.6 a) Man kann sich vorstellen, in w werden gewisse Symbole markiert, und zwar mindestens |Q| St¨ uck. Dann liegt mindestens eine Marke in einem Teilwort, das gepumpt werden kann. b) Der Beweis ist w¨ortlich derselbe wie beim Pumping-Lemma, nur daß die dort benutzte Menge P nicht mehr notwendig gleich {0, . . . , m} ist. Beispiel 6.7 Die Sprache L = {an bm cm | n ∈ N, m ∈ N0 } ist nicht regul¨ar. Angenommen, L werde von einem Automaten mit m = |Q| Zust¨anden erkannt. Dann gilt abm cm ∈ L und P = {2, 3, . . . , m + 1} erf¨ ullt |P | ≥ |Q|. F¨ ur die m m Zerlegung xyz = ab c muß eine der Positionen aus P im Teilwort y liegen. Daher ist der Fall x = ε und y = a ausgeschlossen. Also ist y ein nichtleeres Teilwort von bm cm . Dann liegt aber xy k z f¨ ur k > 1 sicherlich nicht mehr in L. Die Argumentation l¨aßt sich aber auch mit dem Pumping-Lemma f¨ uhren: Der Fall x = ε in der Zerlegung von abm cm erzwingt wegen y 6= ε, daß z ein Suffix von bm cm ist. Dann liegt aber xz nicht in L. Daher muß y = bν cµ ein nichtleeres Teilwort von bm cm sein. Dies kann aber innerhalb von L nicht gepumpt werden. (Nat¨ urlich klappt der Nachweis auch mit Hilfe des syntaktischen Monoids.) Lemma 6.8 Ogden-Lemma fu ¨ r kontextfreie Sprachen Es sei L = L(G) f¨ ur eine kontextfreie Grammatik G = (V, X, R, S). Dann gibt es eine Konstante p ∈ N, so daß f¨ ur jedes z ∈ L und jede Menge P ausgezeichneter Positionen in z mit |P | ≥ p eine Zerlegung Φ = (u, v, w, x, y) von z existiert, so daß gilt: Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

6 PUMPING-LEMMA UND FOLGERUNGEN 1. Es gibt ein A ∈ V mit S →∗ uAy, A →∗ vAx und A →∗ w. 2. F¨ ur alle ν ∈ N0 gilt uv ν wxν y ∈ L. 3. Die Anzahl der Positionen aus P , die bez¨ uglich der Zerlegung Φ im zweiten, dritten oder vierten Teilwort liegen, ist durch p beschr¨ankt. 4. Jedes der Worte u, v, w oder jedes der Worte w, x, y enth¨alt eine ausgezeichnete Position aus P . Bemerkung 6.9 a) Die Aussage 2. folgt offensichtlich aus der ersten. Die Aussage 4. verhindert eine triviale Zerlegung von z. Die Aussage 3. erlaubt eine genauere Festlegung der Pumpstellen. b) Das folgende Pumping-Lemma wurde historisch vor dem Ogden-Lemma bewiesen. Folgerung 6.10 Pumping-Lemma fu ¨ r kontextfreie Sprachen Es sei L eine kontextfreie Sprache. Dann gibt es eine Konstante p ∈ N, so daß f¨ ur jedes z ∈ L mit `(z) ≥ p eine Zerlegung (u, v, w, x, y) von z existiert mit den Eigenschaften (43) (44) (45)

u, v, w ∈ X + ∨ w, x, y ∈ X + 0 < `(vwx) ≤ p ν ν uv wx y ∈ L f¨ ur jedes ν ∈ N0 .

Beweis: Die Aussage folgt unmittelbar aus dem Ogden-Lemma, indem man f¨ ur P s¨amtliche Positionen in z nimmt. Beispiel 6.11 Die Sprache L = {an bn cn | n ∈ N0 } ist nicht kontextfrei. Angenommen, L w¨are kontextfrei und p eine Konstante wie im Pumping-Lemma. F¨ ur z = ap bp cp existiert dann eine Zerlegung z = uvwxy mit den Bedingungen (43) - (45). Es m¨ ussen v und x in {a}∗ ∪ {b}∗ ∪ {c}∗ liegen, da sonst (45) nicht erf¨ ullt sein kann. Es k¨onnen also maximal zwei der Buchstaben a, b oder c aus z gepumpt werden, was wegen der Definition von L nur m¨oglich ist, wenn keiner der Buchstaben gepumpt wird. Dann w¨are aber v = x = ε, was aufgrund von (43) ausgeschlossen ist. Aus dem Ogden-Lemma bzw. dem Pumping-Lemma ergeben sich sofort Aussagen u ur kontextfreie Grammatiken. ¨ber die Entscheidbarkeit einiger Fragen f¨ Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

6 PUMPING-LEMMA UND FOLGERUNGEN

Folgerung 6.12 Zu jeder kontextfreien Grammatik G = (V, X, R, S) existiert S eine Konstante p ∈ N so daß f¨ ur M = pk=0 X k gilt: 1. L(G) = ∅ ⇐⇒ L(G) ∩ M = ∅, 2. |L(G)| < ∞ ⇐⇒ L(G) ⊆ M ⇐⇒ L(G) ∩ (X ∗ \ M ) = ∅. Satz 6.13 a) F¨ ur eine beliebige kontextfreie Grammatik G und einen beliebigen endlichen Automaten A ist jede der folgenden Fragen entscheidbar: 1. L(G) = ∅, 2. |L(G)| < ∞, 3. L(G) ∩ L(A) = ∅, 4. L(G) ⊆ L(A). b) Dagegen sind die folgenden Fragen nicht entscheidbar: 5. L(A) ⊆ L(G), 6. L(A) = L(G). c) Weiterhin sind f¨ ur zwei beliebige kontextfreie Grammatiken G1 und G2 die folgenden Fragen nicht entscheidbar: 7. L(G1 ) ⊆ L(G2 ), 8. L(G1 ) = L(G2 ), 9. L(G1 ) ∩ L(G2 ) = ∅, 10. L(G1 ) ∩ L(G2 ) ist kontextfrei, 11. X ∗ \ L(G1 ) ist kontextfrei, 12. L(G1 ) ist regul¨ar, 13. L(G1 ) ist deterministisch. Lemma 6.14 Pumping-Lemma fu ¨ r lineare Sprachen Sei G = (V, X, R, S) eine lineare Grammatik und L = L(G). Dann gibt es eine Konstante p ∈ N, so

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

6 PUMPING-LEMMA UND FOLGERUNGEN

daß f¨ ur jedes z ∈ L mit `(z) ≥ p eine Zerlegung Φ = (u, v, w, x, y) von z existiert, so daß gilt: (46) (47) (48)

`(uv) ≤ p ∧ `(xy) ≤ p 0 < `(vx) ≤ p uv ν wxν y ∈ L f¨ ur jedes ν ∈ N0 .

Beispiel 6.15 Die Sprache L = {an bn cm dm | n, m ∈ N0 } ist nicht linear. Angenommen, L w¨are linear und p eine Konstante wie im Pumping-Lemma. F¨ ur p p p p z = a b c d existiert dann eine Zerlegung z = uvwxy mit den Bedingungen (46) ussen v und x in {a}∗ ∪ {b}∗ ∪ {c}∗ ∪ {d}∗ liegen, da sonst (48) nicht - (48). Es m¨ erf¨ ullt sein kann. Es k¨onnen also maximal zwei der Buchstaben a, b, c oder d aus z gepumpt werden. Nach Definition von L gilt also entweder v, x ∈ {a}∗ ∪ {b}∗ oder v, x ∈ {c}∗ ∪ {d}∗ . Im ersten Fall enthielte y das Teilwort cp dp , im zweiten Fall enthielte u das Teilwort ap bp . Beides widerspricht jeweils (46).

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

¨ 7 WEITERE VERKNUPFUNGEN FORMALER SPRACHEN

7

Weitere Verknu ¨ pfungen formaler Sprachen

F¨ ur manche Zwecke ist es n¨ utzlich, neben den in Definition 1.16 bereits betrachteten Operationen weitere mengentheoretische Verkn¨ upfungen formaler Sprachen zu betrachten. Die grundlegenden Eigenschaften dieser Verkn¨ upfungen wie Assoziativit¨at, Kommutativit¨at, Idempotenz oder gegenseitige Distributivit¨at sind jeweils elementar nachzurechnen. Erheblich schwieriger ist die Abgeschlossenheit von Sprachklassen gegen¨ uber diesen Operationen zu u ufen. Sie interessiert ¨berpr¨ allerdings meistens auch nur in speziellen Situationen. Definition 7.1 Sind L1 , L2 ⊆ X ∗ Sprachen u ¨ber dem Alphabet X, so nennt man L1 ∆L2 = (L1 \ L2 ) ∪ (L2 \ L1 ) die symmetrische Differenz von L1 und L2 und, falls X mindestens zwei Symbole, beispielsweise 1 und 2, enth¨alt, nennt man L1 ⊕ L2 = {w = 1v ∈ X ∗ | v ∈ L1 } ∪ {w = 2v ∈ X ∗ | v ∈ L2 } die markierte Vereinigung von L1 und L2 . Ist weiterhin # ∈ / X ein neues Symbol, so heißt L1 #L2 = {w1 #w2 ∈ (X ∪ {#})∗ | wi ∈ Li } die markierte Konkatenation oder das markierte Produkt von L1 und L2 . Hiermit ur Sprachen L ⊆ X ∗ definiert. ist dann auch die markierte ∗-Operation L∗# f¨ Definition 7.2 F¨ ur jede Sprache L u ¨ber dem Alphabet X seien die folgenden Sprachen definiert (49) M AX(L) (50) M IN (L) (51) AN F (L) (52) EN D(L) (53) T EIL(L) (54) ZY KEL(L)

= = = = = =

{w {w {w {w {w {w

∈ X∗ ∈ X∗ ∈ X∗ ∈ X∗ ∈ X∗ ∈ X∗

| ∀v ∈ X + : wv ∈ / L} ∗ | ∀u ∈ X , v ∈ X + : uv = w ⇒ u ∈ / L} ∗ | ∃v ∈ X : wv ∈ L} | ∃v ∈ X ∗ : vw ∈ L} | ∃u, v ∈ X ∗ : uwv ∈ L} | ∃u, v ∈ X ∗ : w = uv ∧ vu ∈ L}

Folgerung 7.3 Die Klasse der regul¨aren Sprachen ist abgeschlossen unter diesen Operationen. Eine ganz andere M¨oglichkeit, aus gegebenen formalen Sprachen neue zu gewinnen bieten die Substitutionen und Homomorphismen. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

¨ 7 WEITERE VERKNUPFUNGEN FORMALER SPRACHEN Definition 7.4 Es seien X und Y Alphabete. Eine Abbildung σ : X ∗ → P(Y ∗ ) heißt Substitution, falls (55) σ(ε) 6= ∅ und (56) σ(vw) = σ(v)σ(w) f¨ ur alle v, w ∈ X ∗ gilt. (Auf der rechten Seite der letzten Gleichung ist offensichtlich die Konkatenation von Sprachen u ¨ber Y gemeint.) Ist σ(x) endlich f¨ ur alle x ∈ X, so nennt man die Substitution σ endlich. F¨ ur jede Sprache L ⊆ X ∗ definiert man die Sprache σ(L) ⊆ Y ∗ durch (57) σ(L) =

[

σ(w).

w∈L

Bemerkung 7.5 a) Aus σ(ε) = ∅ und (56) w¨ urde offensichtlich σ(v) = σ(vε) = σ(v)∅ = ∅ f¨ ur alle v ∈ X ∗ folgen. Die Bedingung (55) schließt also nur diesen trivialen Fall aus. uglich des Produktes in P(Y ∗ ) b) Andererseits muß σ(ε) wegen (56) eine bez¨ idempotente Teilmenge von Y ∗ sein. Dies ist aber dann nur noch f¨ ur (58) σ(ε) = {ε} m¨oglich. c) Gilt nun ε ∈ / σ(x) f¨ ur alle x ∈ X, so folgt aus (56) f¨ ur jedes w = x1 . . . xn ∈ X + bereits ε ∈ / σ(w) = σ(x1 . . . xn ) = σ(x1 ) . . . σ(xn ). Dies gibt Anlaß zu der folgenden Definition 7.6. d) Ist σ(x) endlich f¨ ur jedes x ∈ X, so ist wegen (56) σ(w) endlich f¨ ur jedes w ∈ X +. e) Ist σ(x) = {y} einelementig f¨ ur jedes x ∈ X, so schreibt man kurz σ(x) = y, und (56) zeigt dann, daß durch σ ein gew¨ohnlicher Homomorphismus σ : X ∗ → Y ∗ gegeben wird. Der Begriff der Substitution verallgemeinert also in diesem Sinne den Begriff des Homomorphismus.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

¨ 7 WEITERE VERKNUPFUNGEN FORMALER SPRACHEN Definition 7.6 Eine Substitution σ : X ∗ → P(Y ∗ ) heißt ε-frei, wenn (59) ε ∈ σ(w) ⇒ w = ε gilt. Lemma 7.7 Zu jeder Abbildung s : X → P(Y ∗ ) gibt es eine eindeutig bestimmte Substitution σ : X ∗ → P(Y ∗ ) mit (60) σ(x) = s(x) f¨ ur alle x ∈ X. Insbesondere ist jede Substitution σ bereits durch die Angabe der Bilder σ(x) ∈ P(Y ∗ ) f¨ ur alle x ∈ X eindeutig bestimmt. Wegen Bemerkung 7.5 e) gilt die entsprechende Aussage f¨ ur beliebige Abbildungen s : X → Y und Homomorphismen ∗ ∗ σ:X →Y . Beweis: Wegen (56) gilt f¨ ur jeden Homomorphismus σ mit (60) bereits σ(x1 . . . xn ) = σ(x1 ) . . . σ(xn ) = s(x1 ) . . . s(xn ) f¨ ur alle x1 . . . xn ∈ X + . Zusammen mit (58) ist σ damit eindeutig bestimmt. Andererseits wird hierdurch auch offensichtlich ein Homomorphismus σ : X ∗ → P(Y ∗ ) definiert. Beispiel 7.8 Es seien X = {a, b}, Y = {|} und der (ε-freie) Homomorphismus σ : X ∗ → Y ∗ durch σ(a) = σ(b) = || gegeben. F¨ ur die lineare, aber nicht regul¨are n n Sprache L = {a b | n ∈ N0 } gilt dann σ(L) = {|n | n ∈ 4N0 } = L0 und σ −1 (L0 ) = {w ∈ X ∗ | `(w) ∈ 2N0 } ⊃ L, und diese beiden Sprachen sind regul¨ar. Beispiel 7.9 Es seien X = {a, b}, Y = {0, 1, b} und die (ε-freie) Substitution σ : X ∗ → P(Y ∗ ) durch σ(a) = {0, 1}, σ(b) = {b} definiert. F¨ ur L = {an bn | n ∈ N0 } ist dann σ(L) = {wbn | w ∈ {0, 1}∗ , `(w) = n}. Satz 7.10 F¨ ur i = 0, 1, 2, 3 gilt: Ist L ⊆ X ∗ eine Typ-i-Sprache und σ : X ∗ → ∗ P(Y ) eine Substitution, so daß σ(x) f¨ ur alle x ∈ X eine Typ-i-Sprache ist, dann ist σ(L) eine Typ-i-Sprache.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

¨ 7 WEITERE VERKNUPFUNGEN FORMALER SPRACHEN

Satz 7.11 Die Klassen der linearen und der metalinearen Sprachen sind nicht abgeschlossen unter Substitutionen. Beweis: F¨ ur X = {a, b} ist L = {ak | k ∈ N} regul¨ar und damit linear. Die Sprache La = {an bn | n ∈ N} ist ebenfalls linear und die endliche Sprache Lb = {b} auch. Nat¨ urlich sind alle diese Sprachen erst recht metalinear. Durch σ(a) = La und σ(b) = Lb wird eine Substitution σ : X ∗ → X ∗ gegeben, aber es ist [

σ(L) =

σ(w) = {an1 bn1 . . . ank bnk | k, ni ∈ N}

w∈L

nicht einmal metalinear. Satz 7.12 Ist L ⊆ X ∗ eine Typ-1-Sprache und σ : X ∗ → P(Y ∗ ) eine Substiur alle x ∈ X eine Typ-2-Sprache ist, dann ist σ(L) nicht tution, so daß σ(x) f¨ notwendig eine Typ-1-Sprache. Der Beweis beruht im wesentlichen darauf, die Grammatik G f¨ ur eine nicht εfreie Typ-0-Sprache, die also keine Typ-1-Sprache ist, zu einer Grammatik G0 zu modifizieren, die vom Typ 1 ist. Dann wird durch eine ebenfalls nicht εfreie Substitution die Typ-1-Sprache L = L(G0 ) auf die Typ-0-Sprache L(G) abgebildet. Satz 7.13 F¨ ur jede Typ-0-Sprache L ⊆ X ∗ gibt es eine Typ-1-Sprache L0 ⊆ X ∗ und einen Homomorphismus σ : X ∗ → X ∗ mit σ(L0 ) = L. Beispiel 7.14 Es sei k ∈ N und das Alphabet Xk = {(i , )i | i = 1, . . . , k} bestehe aus k Klammerpaaren. Weiterhin sei G = ({S}, Xk , Rk , S) die Grammatik mit der Regelmenge Rk = {S → ε, S → SS} ∪ {S → (i S)i | i = 1, . . . , k}. Dann heißt Dk = L(G) eine Dyck-Sprache mit k Klammerpaaren (Walther von Dyck, 1856 - 1934). Sie ist offensichtlich kontextfrei, aber nicht metalinear. Die schon mehrfach benutzte kontextfreie, aber nicht regul¨are Sprache {an bn | n ∈ N0 } entsteht als Durchschnitt der regul¨aren Sprache {a}∗ {b}∗ mit der Dyck-Sprache D1 mit dem Klammerpaar a = (1 und b =)1 (vgl. den folgenden Satz 7.16). Beispiel 7.15 Es sei D2 die Dyck-Sprache mit den 2 KLammerpaaren X2 = {(, ), [, ]} und Dk eine Dyck-Sprache mit den k Klammerpaaren Xk = {(i , )i | i = 1, . . . , k}. Durch σ((i ) = [(. . . ([ und σ()i ) =]) . . .)], wobei jeweils genau i runde Klammern zwischen den beiden eckigen Klammern stehen, wird ein Homomorphismus σ : Xk∗ → X2∗ definiert. Offensichtlich gilt σ(Dk ) ⊆ D2 und σ(Xk∗ \ Dk ) ⊆ X2∗ \ D2 , also Dk = σ −1 (D2 ). Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

¨ 7 WEITERE VERKNUPFUNGEN FORMALER SPRACHEN

Satz 7.16 Chomsky-Schu ¨ tzenberger Zu jeder kontextfreien Sprache L gibt es eine Dyck-Sprache Dk mit k Klammerpaaren, eine regul¨are Sprache R(L) und einen Homomorphismus σ mit L = σ(Dk ∩ R(L)). Definition 7.17 Eine kontextfreie Grammatik G = (V, X, R, S) ist in GreibachNormalform, wenn alle Regeln aus R von der Form S → ε oder A → w mit A ∈ V und w ∈ X(V \ {S})∗ sind. Satz 7.18 Jede kontextfreie Grammatik ist ¨aquivalent zu einer Grammatik in Greibach-Normalform. Satz 7.19 Greibach Es gibt eine kontextfreie Sprache H, so daß zu jeder kontextfreien Sprache L ein Homomorphismus σ existiert mit L = σ −1 (H).

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

8 DER SATZ VON PARIKH

8

Der Satz von Parikh

Definition 8.1 W¨orter v = a1 . . . an und w = b1 . . . bn u ¨ber einem Alphabet X heißen symbol¨aquivalent, wenn eine Permutation π ∈ Sn mit ai = bπ(i) f¨ ur i = 1, . . . , n existiert. Bemerkung 8.2 Offensichtlich ist die Symbol¨aquivalenz eine Kongruenzrelation auf der freien Halbgruppe (X ∗ , ·). F¨ ur jedes n ∈ N0 zerf¨allt dabei X n ⊂ X ∗ in disjunkte Klassen. Genau f¨ ur |X| = 1 handelt es sich bei der Symbol¨aquivalenz daher um die identische Relation. Definition 8.3 Es sei X = {x1 , . . . , xk } ein Alphabet. F¨ ur jedes xi ∈ X und ∗ w = y1 . . . yn ∈ X sei `xi (w) = |{j | yj = xi }|. Die Abbildung Ψ : X ∗ → Nk0 mit Ψ(w) = (`x1 (w), . . . , `xk (w)) heißt Parikh-Abbildung zu X. F¨ ur jede Sprache ∗ L ⊆ X heißt Ψ(L) Parikh-Bild von L. Bemerkung 8.4 a) F¨ ur beliebige W¨orter v, w ∈ X ∗ und jedes x ∈ X gilt offensichtlich `x (vw) = `x (v) + `x (w), d. h. `x : X ∗ → N0 ist ein surjektiver Halbgruppenhomomorphismus von (X ∗ , ·) auf (N0 , +). Daher ist auch jede ParikhAbbildung ein surjektiver Halbgruppenhomomorphismus. Die Symbol¨aquivalenz ist gerade die zu diesem Homomorphismus geh¨orende Kongruenzrelation auf (X ∗ , ·) (vgl. (61)). b) Die Parikh-Abbildung h¨angt von der konkreten Numerierung der Elemente von X ab. Zu jedem Alphabet X mit |X| > 1 gibt es also verschiedene ParikhAbbildungen. Aussagen u ¨ber die Parikh-Bilder von Sprachen sind also nur dann sinnvoll, wenn sie unabh¨angig von der Numerierung der Elemente sind. Lemma 8.5 Es sei Ψ eine Parikh-Abbildung zum Alphabet X. Dann gilt f¨ ur ∗ alle v, w ∈ X (61) v symbol¨aquivalent zu w ⇐⇒ Ψ(v) = Ψ(w). Weiterhin gelten f¨ ur Sprachen L1 , L2 ⊆ X ∗ (62) Ψ(L1 ∪ L2 ) = Ψ(L1 ) ∪ Ψ(L2 ) (63) Ψ(L1 L2 ) = Ψ(L1 ) + Ψ(L2 ) = Ψ(L2 L1 ) (64) Ψ((L1 ∪ L2 )∗ ) = Ψ(L∗1 L∗2 ). Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

8 DER SATZ VON PARIKH

Beweis: (61): v und w sind genau dann symbol¨aquivalent, wenn f¨ ur alle x ∈ X schon `x (v) = `x (w) gilt. Dies ist aber gleichwertig zu Ψ(v) = Ψ(w). (62): Dies gilt sogar f¨ ur beliebige Abbildungen Ψ. (63): Dies folgt aus Bemerkung 8.4 a). (64): Dies folgt unmittelbar aus der Implikation ∀w ∈ X ∗ : w ∈ (L1 ∪ L2 )∗ =⇒ ∃u ∈ L∗1 , v ∈ L∗2 : Ψ(w) = Ψ(uv), denn wegen L∗1 L∗2 ⊆ (L1 ∪ L2 )∗ ist Ψ(L∗1 L∗2 ) ⊆ Ψ((L1 ∪ L2 )∗ ) klar. Zum Nachweis S dieser Implikation betrachte man f¨ ur w ∈ (L1 ∪ L2 )∗ = k∈N0 (L1 ∪ L2 )k die Darstellung w = u1 . . . uk mit ui ∈ L1 ∪ L2 f¨ ur i ∈ I = {1, . . . , k}. Es gibt dann eine Teilmenge J = {j1 , . . . , jm } ⊆ I mit ui ∈ L1 f¨ ur i ∈ J und ui ∈ L2 f¨ ur i ∈ I \ J = {i1 , . . . , in }. Mit u = uj1 . . . ujm ∈ L∗1 und v = ui1 . . . uin ∈ L∗2 ist dann w symbol¨aquivalent zu uv, d. h. es gilt Ψ(w) = Ψ(uv). Definition 8.6 Es sei X = {x1 , . . . , xk } ein Alphabet und Ψ : X ∗ → Nk die zugeh¨orige Parikh-Abbildung. Sprachen L, L0 ⊆ X ∗ heißen symbol¨aquivalent, wenn Ψ(L) = Ψ(L0 ) gilt. Definition 8.7 Eine Menge K ⊆ Nk0 ⊂ Rk heißt linear, wenn es α0 , . . . , αm ∈ Nk0 gibt, so daß gilt K = {α0 +

m X

ni αi | ni ∈ N0 , i = 1, . . . , m}.

i=1

Ist K endliche Vereinigung linearer Mengen, so nennt man K semilinear. Lemma 8.8 Mit K1 , K2 ⊆ Nk0 sind auch K1 ∪ K2 und K1 + K2 semilinear. Beweis: Die Behauptung u ¨ber die Vereinigung ist nach Definition semilinearer Mengen richtig. Sind

K1 = {α0 + K2 = {β0 +

m X

ni αi | ni ∈ N0 , i = 1, . . . , m} und

i=1 r X

ni αi | ni ∈ N0 , i = m + 1, . . . , r}

i=m+1

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

8 DER SATZ VON PARIKH

schon linear, so ist auch K1 + K2 = {(α0 + β0 ) +

r X

ni αi | ni ∈ N0 , i = 1, . . . , r}

i=1

linear, also erst recht semilinear. Wegen (M1 ∪ M2 ) + M3 = (M1 + M3 ) ∪ (M2 + M3 ) f¨ ur beliebige lineare Mengen folgt hieraus dann die Behauptung auch f¨ ur semilineare Mengen Ki . Satz 8.9 Jedes Parikh-Bild einer regul¨aren Sprache ist semilinear. Jede semilineare Menge ist Parikh-Bild einer regul¨aren Sprache. Beweisidee: Die erste Aussage wird durch Induktion nach dem Aufbau einer regul¨aren Sprache L gef¨ uhrt, wobei Lemma 8.5 und Lemma 8.8 benutzt werden. F¨ ur den Beweis der zweiten Aussage wird zu einer gegebenen linearen Menge K eine linkslineare Grammatik G angegeben, die Ψ(L(G)) = K erf¨ ullt. Folgerung 8.10 Mit K1 , K2 ⊆ Nk0 sind auch K1 ∩ K2 und Nk0 \ K1 semilinear. Der Beweis des folgenden Satzes von Parikh benutzt die bisher bewiesenen Aussagen und weitere Aussagen f¨ ur kontextfreie Grammatiken, das Ogden-Lemma bzw. das daraus folgende Paarungs-Lemma. Die Beweise hierf¨ ur sind technisch aber etwas aufwendiger und werden innerhalb dieser Vorlesung nicht gef¨ uhrt. Man findet sie in dem Buch Einf¨ uhrung in die Automatentheorie und Theorie formaler Sprachen von L. Balke und K. H. B¨ohling. Satz 8.11 (Satz von Parikh) Jede kontextfreie Sprache L besitzt ein semilineares Parikh-Bild, d. h. L ist symbol¨aquivalent zu einer regul¨aren Sprache. Folgerung 8.12 F¨ ur ein Alphabet X mit |X| = 1 stimmen die regul¨aren mit den kontextfreien Sprachen u ¨berein. Beweis: Da jede regul¨are Sprache kontextfrei ist, bleibt die Umkehrung zu zeigen. Sei also L ⊆ {a}∗ eine kontextfreie Sprache. Dann gibt es nach dem Satz von Parikh eine regul¨are Sprache L0 ⊆ {a}∗ und eine Parikh-Abbildung Ψ : {a}∗ → N0 mit Ψ(L) = Ψ(L0 ). Mit Bemerkung 8.2 und (61) folgt hieraus bereits L = L0 . Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

9 LINDENMAYER-SYSTEME

9

Lindenmayer-Systeme

Neben den Semi-Thue-Systemen und den Regelgrammatiken, bei denen die Ableitungen der W¨orter einer formalen Sprache “seriell” erfolgen, gibt es auch Systeme, bei denen “parallele” Ableitungen benutzt werden. Derartige Regelsysteme wurden erstmals 1968 durch den Botaniker Aristid Lindenmayer eingef¨ uhrt, der damit das Wachstum von einfachen Pflanzen simulieren wollte. Sie werden daher heute meist nach ihm benannt. Viele biologische Anwendungen f¨ ur LindenmayerSysteme (einschließlich Erweiterungen der hier behandelten Formen) findet man in dem Buch A. Lindenmayer, P. Prusienkiewicz, The Algorithmic Beauty of Plants, Springer 1990. Definition 9.1 Ein kontextfreies Lindenmayer-System oder kurz 0L-System L = (X, P, w) besteht aus einem Alphabet X, einer endlichen Menge P ⊆ X × X ∗ von Produktionsregeln und einem Startwort oder Axiom w ∈ X + . Ist f¨ ur ein x ∈ X keine Regel (x, y) in P vorhanden, so werde die triviale Regel (x, x) hinzugenommen. Gibt es dann f¨ ur jedes x ∈ X genau eine Regel (x, y) ∈ P , so heißt das Lindenmayer-System deterministisch oder ein D0L-System. Definition 9.2 Ist L = (X, P, w) ein 0L-System, dann wird die Ableitbarkeitsrelation → auf X ∗ durch x → y ⇐⇒ x = x1 . . . xn , y = y1 . . . yn ∈ X ∗ , (xi , yi ) ∈ P, i = 1, . . . , n definiert. Bezeichnet man mit →∗ wiederum die reflexive und transitive H¨ ulle dieser Relation, so wird die von L erzeugte Sprache definiert durch L(L) = {z ∈ X ∗ | w →∗ z}. Bemerkung 9.3 Insbesondere gilt also w ∈ L(L) f¨ ur das Axiom w, d. h. es ist stets L(L) 6= ∅. Die Regeln (x, y) ∈ P notiert man auch in der Form x → y. Ist X ein beliebiges Alphabet und P = {x → x | x ∈ X}, so ist L = (X, P, w) f¨ ur jedes w ∈ X + ein deterministisches 0L-System mit L(L) = {w}. Folgerung 9.4 Es sei L = (X, P, w) ein 0L-System mit L = L(L). Ersetzt man dann jede Regel x → y aus P durch die Regel x → y und faßt diese “gespiegelten” Regeln zu der Regelmenge P zusammen, so ist L = (X, P , w) ein 0L-System, das die Spiegelsprache L erzeugt. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

9 LINDENMAYER-SYSTEME

Beispiel 9.5 Es sei X = {a} ein einelementiges Alphabet. Das nichtdeterministische 0L-System L = (X, {a → ε, a → a}, an ) f¨ ur ein festes n ∈ N erzeugt 2 n die endliche Sprache Ln = L(L) = {ε, a, a , . . . , a }. Versucht man, Ln f¨ ur n ≥ 2 durch ein deterministisches 0L-System zu beschreiben, so kann man als Startwort w = ak ∈ Ln f¨ ur ein festes k ∈ {1, . . . , n} w¨ahlen. Um ε ∈ Ln abzuleiten, muß man als einzige Regel in P die Ableitung a → ε nehmen. Dann ist neben dem Startwort ak aber einzig das leere Wort ε ableitbar und daher L(L) 6= Ln . Man sieht hieran auch sofort, daß die einzigen endlichen Sprachen u ¨ber X, die von 0L-Systemen erkannt werden, neben den Sprachen Ln die einelementigen Sprachen {an } und die zweielementigen Sprachen {ε, an } sind. Also ist die Klasse von Sprachen, die durch nichtdeterministische 0L-Systeme erzeugt werden k¨onnen, echt gr¨oßer, als die Klasse von Sprachen, die sich deterministisch erzeugen lassen. Außerdem sieht man, daß nicht jede endliche (und damit auch nicht jede regul¨are) Sprache L 6= ∅ durch ein D0L-System erzeugt werden kann. Dieselbe Aussage gilt auch f¨ ur nichtdeterministische Lindenmayer-Systeme, wie man anhand der zweielementigen Sprache L = {a, a3 } sofort u ufen ¨berpr¨ kann. Also ist die Klasse der Sprachen, die von (deterministischen) LindenmayerSystemen erzeugt werden, nicht abgeschlossen gegen¨ uber der Vereinigung. Beispiel 9.6 Es sei L = ({a, b}, {a → a, b → aba}, b), also ein D0L-System gegeben. Dann ist L(L) = {an ban | n ∈ N0 } eine kontextfreie, nichtregul¨are Sprache. Die Klasse von Sprachen, die von D0L-Systemen erzeugt werden, ist also nicht in der Klasse der regul¨aren Sprachen enthalten. Beispiel 9.7 F¨ ur das D0L-System L = ({a, b, c}, {a → abcc, b → bcc, c → c}, a) ist L = L(L) = {a, abcc, abccbcccc, abccbccccbcccccc, . . .} eine nicht-kontextfreie Sprache, wie aus dem Pumping-Lemma leicht folgt. Die L¨angen der Worte aus L bilden genau die Menge der Quadratzahlen. Satz 9.8 Die Klasse der Sprachen, die von 0L-Systemen erzeugt wird, ist nicht abgeschlossen gegen¨ uber Vereinigung, ε-freien Homomorphismen, inversen Homomorphismen und Durchschnitt mit regul¨aren Sprachen. Satz 9.9 Gilt L = L(L) f¨ ur ein 0L-System L = (X, P, w), so ist L eine Typ-1Sprache.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

9 LINDENMAYER-SYSTEME

Beweisidee: Es sei G = ({X0 , X1 , X2 , X3 }, X, R, X0 ), wobei R aus den folgenden Produktionsregeln bestehe (1) X0 → X1 wX1 , X1 → ε, X1 a → X1 X2 a f¨ ur alle a ∈ X, X1 X2 → X3 X1 , aX3 → X3 a f¨ ur alle a ∈ X, X1 X3 → X1 , (2) X2 a → bX2 f¨ ur alle a → b aus P . Diese Grammatik ist eine Typ-1-Grammatik und es gilt L(G) = L, was man leicht u uft. ¨berpr¨ Genau wie bei Regelgrammatiken kann man auch f¨ ur Lindenmayer-Systeme die Produktionsregeln kontextsensitiv gestalten. Man gelangt dann zu 2L-Systemen (falls der “Kontext” auf beiden Seiten des abzuleitenden Buchstabens steht) und zu 1L-Systemen (falls der Kontext nur auf einer Seite ber¨ ucksichtigt wird). Man kann dann zeigen, daß die 2L-Systeme mehr Sprachen erzeugen k¨onnen als die 1L-Systeme, und diese wiederum mehr als die 0L-Systeme. Eine andere, biologisch sinnvolle Erweiterung von 0L-Systemen besteht darin, mehrere Mengen von Produktionsregeln zuzulassen, von denen jeweils immer genau eine “aktiv” ist. Dies entspricht in biologischen Anwendungen dem Vorliegen verschiedener Entwicklungsstadien in dem Wachstumsprozeß. Definition 9.10 Ein T 0L-System L = (X, T, w) besteht aus einem Alphabet X, einem Startwort w ∈ X + und einer endlichen, nichtleeren Menge T endlicher Teilmengen von X × X ∗ , wobei jede Tabelle t ∈ T die Vollst¨andigkeitsbedingung erf¨ ullt: F¨ ur jedes x ∈ X gibt es ein Paar (x, y) ∈ t mit y ∈ X ∗ . Falls es stets genau ein derartiges Paar gibt, heißt L ein deterministisches oder DT 0L-System Die Ableitbarkeitsrelation → auf X ∗ wird durch x → y ⇐⇒ ∃t ∈ T : x = x1 . . . xn , y = y1 . . . yn ∈ X ∗ , (xi , yi ) ∈ t, i = 1, . . . , n definiert. Bezeichnet man mit →∗ wiederum die reflexive und transitive H¨ ulle dieser Relation, so wird die von L erzeugte Sprache definiert durch L(L) = {z ∈ X ∗ | w →∗ z}. Beispiel 9.11 F¨ ur das T 0L-System L = ({a}, {{a → a2 }, {a → a3 }}, a) ist L = L(L) = {an | n = 2i 3j , i, j ∈ N0 }. Dieses T 0L-System ist deterministisch, da jede Tabelle deterministisch ist, und L kann von keinem 0L-System erzeugt werden. Bemerkung 9.12 Da jedes 0L-System ein T 0L-System mit nur einer einzigen Tabelle ist, wird die Klasse der erzeugbaren Sprachen echt gr¨oßer. Aber auch f¨ ur diese gr¨oßere Klasse gilt ein Satz analog zu Satz 9.8. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

10 WEITERE ARTEN ENDLICHER AUTOMATEN

10

Weitere Arten endlicher Automaten

¨ Eine andere Art von Nichtdeterminismus bei der Ubergangsfunktion endlicher Automaten wird durch die stochastischen Automaten beschrieben. Eine ausf¨ uhrliche Darstellung stochastischer Automaten findet man in dem Buch von Rais G. Bukharaev, Theorie der stochastischen Automaten, Teubner 1995. Definition 10.1 Es sei A eine beliebige nichtleere Menge. Eine Abbildung P : P(A) → I heißt diskretes Wahrscheinlichkeitsmaß auf A, wenn die folgenden Bedingungen gelten (65)

P (A) = 1,

(66) P (

∞ [

i=1

(67)

Ai ) =

∞ X

P (Ai ), falls Ai ⊆ A paarweise disjunkt,

i=1

supp(P ) = {a ∈ A | P (a) > 0} ist abz¨ahlbar.

Mit Wd (A) werde die Menge aller diskreten Wahrscheinlichkeitsmaße auf A bezeichnet. Definition 10.2 Ein stochastischer Automat (ohne Ausgabe) A = (Q, X, h) besteht aus einem Eingabealphabet X, einer (endlichen oder abz¨ahlbar unendlichen) Zustandsmenge Q und einer Funktion h : Q × X → Wd (Q). Bemerkung 10.3 a) In der Literatur werden auch stochastische Automaten mit abz¨ahlbaren Zustandsmengen betrachtet. Dann erfordert die folgende Darstellung f¨ ur stochastische Automaten die Behandlung abz¨ahlbar unendlicher stochastischer Matrizen. b) Ebenso werden stochastische Automaten mit Ausgabefunktionen betrachtet, die die Begriffe der Mealy- und Moore-Automaten verallgemeinern. c) Befindet sich ein stochastischer Automat im Zustand q und wird das Eingabezeichen x gelesen, so gibt h(q, x)(q 0 ) = p(q 0 | q, x) die Wahrscheinlichkeit daf¨ ur an, daß q 0 der Folgezustand ist. Es gilt also 0 ≤ p(q 0 | q, x) ≤ 1 und P 0 ur alle (q, x) ∈ Q × X. Im Fall k = |Q| sind daher die f¨ ur q 0 ∈Q p(q | q, x) = 1 f¨ jedes x ∈ X definierten k × k-Matrizen A(x) = (aq,q0 (x)) = (p(q 0 | q, x))

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

10 WEITERE ARTEN ENDLICHER AUTOMATEN

stochastische Matrizen, d. h. alle Eintr¨age sind nicht-negativ und jede Zeilensumme ist gleich 1. Man schreibt dann den stochastischen Automaten in der Form A = (Q, X, {A(x) | x ∈ X}). Sind alle Eintr¨age in den Matrizen A(x) rationale Zahlen, so heißt A rational. Kommt hierbei in jeder Zeile genau ein Eintrag 1 (und sonst alle Eintr¨age 0) vor, so handelt es sich offenbar um eine Beschreibung eines deterministischen endlichen Automaten. Ansonsten ist das Verhalten eines stochastischen Automaten nicht-deterministisch. Als Anfangsverteilung µ(ε) = µ0 eines stochastischen Automaten bezeichnet man einen Vektor µ0 = (p1 , . . . , pk ) mit 0 ≤ pi ≤ 1 und Pk ur an, daß sich der Automat i=1 pi = 1. Es gibt also pi die Wahrscheinlichkeit daf¨ am Anfang in dem Zustand qi befindet. Man definiert dann die Vektoren µ(w) und die Matrizen A(w) f¨ ur jedes w ∈ X ∗ durch A(ε) = E, µ(x) = µ0 A(x) f¨ ur alle x ∈ X und µ(wx) = µ(w)A(x) = µ0 A(w)A(x). Definition 10.4 Es sei A = (Q, X, {A(x) | x ∈ X}) mit k = |Q| ein endlicher stochastischer Automat, µ0 eine Anfangsverteilung, τ = (τ1 , . . . , τk )T ∈ Rk ein Spaltenvektor und λ ∈ [0, 1) ein Schnittpunkt. Dann heißt L = L(A, µ0 , τ, λ) = {w ∈ X ∗ | µ(w)τ > λ} eine von A akzeptierte oder durch A dargestellte Sprache (zum Schnittpunkt λ). Jede derartige Sprache heißt eine stochastische Sprache. Ist dabei A rational und sind alle Eintr¨age in µ0 , τ und λ ebenfalls rational, so heißt die dargestellte Sprache rationale stochastische Sprache. Gibt es eine Teilmenge F ⊆ Q von Endzust¨anden und gilt τi = 1 f¨ ur alle qi ∈ F und τi = 0 sonst, so sagt man, L werde durch A mit der Endzustandsmenge F und dem Schnittpunkt λ dargestellt. Satz 10.5 Ist eine Sprache L darstellbar durch einen endlichen stochastischen Automaten mit der Anfangsverteilung µ0 , so ist sie auch darstellbar durch einen endlichen stochastischen Automaten mit festem Anfangszustand. Satz 10.6 Ist eine Sprache L darstellbar durch einen endlichen stochastischen Automaten mit einem Endvektor τ , der 0 ≤ τi ≤ 1 f¨ ur alle i erf¨ ullt, dann ist sie (bis auf das leere Wort) durch einen endlichen stochastischen Automaten mit einer Menge von Endzust¨anden darstellbar. Satz 10.7 Jede regul¨are Sprache ist eine rationale stochastische Sprache. Satz 10.8 Ist L stochastische und K regul¨are Sprache, so sind L ∩ K und L ∪ K stochastische Sprachen. Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite

10 WEITERE ARTEN ENDLICHER AUTOMATEN

Satz 10.9 Mit L ist auch L stochastisch. Satz 10.10 Die Klasse der stochastischen Sprachen ist u ¨berabz¨ahlbar. Es gibt also nicht-regul¨are stochastische Sprachen. W¨ahrend alle bisher vorgestellten Typen von Automaten eine serielle Arbeitsweise besitzen, gibt es auch Automaten mit paralleler Arbeitsweise. Ein spezieller Typ hiervon sind die zellul¨aren Automaten, ein anderer die neuronalen Netze. Auf beide kann im Rahmen dieser Vorlesung nicht eingegangen werden, stattdessen sei auf die beiden folgenden B¨ ucher verwiesen. Stephen Wolfram, A new kind of science, Wolfram Media, 2002. Dan Patterson, K¨ unstliche neuronale Netze, Prentice Hall, 1997. Auch bei den Lindenmayer-Systemen kann man den Nichtdeterminismus in Form von Wahrscheinlichkeitsverteilungen auf der Regelmenge einf¨ uhren. Dies ist biologisch sinnvoll, da man hierdurch beispielsweise unterschiedliches Wachstum bei verschiedenen Individuen ein und derselben Art modellieren kann. Einzelheiten dazu finden sich ebenfalls in dem schon zitierten Buch von Lindenmayer und Prusienkiewicz.

Vorherige Seite N¨ achste Seite Zuru ¨ ck Erste Seite Letzte Seite