Theoretische Informatik - hs-weingarten.deertel/vorlesungen/thinf/skript.pdf · 4 1 Formale Sprachen und Maschinenmodelle Fangen wir bei den elementaren Bausteinen an. Deﬁnition

Theoretische Informatik

Wolfgang Ertel

28. Oktober 2008

Inhaltsverzeichnis

1 Formale Sprachen und Maschinenmodelle 31.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3 Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.5 Regulare Ausdrucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.6 Der Lexical Analyzer Lex . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.7 Yacc: Yet Another Compiler Compiler . . . . . . . . . . . . . . . . . . . . 201.8 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.9 Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.10 Zusammenfassung zu Sprachen und Maschinenmodellen . . . . . . . . . . . 281.11 Ubungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2 Berechenbarkeit und Komplexitat 342.1 Berechenbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.2 Komplexitatsklassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.3 NP-Vollstandigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.4 Ubungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Aussagenlogik 46

Pradikatenlogik 46

PROLOG 46

Grenzen der Logik 46

Literaturverzeichnis 48

Kapitel 1

Formale Sprachen undMaschinenmodelle

1.1 Grundlagen

Man muss sich Sprachen vorstellen wie einen Legobaukasten. Die Buchstaben des Alphabetsentsprechen elementaren Bausteinen und die Worte, beziehungsweise Satze entsprechengebauten Objekten. Solche Mengen lassen sich mehr oder weniger einfach beschreiben.Zum Beispiel die Menge der Objekte, die nur aus roten Steinen gebaut sind. Oder dieMenge der Objekte bei denen auf einem Basisstein nur Steine oben draufgesetzt werdendurfen, aber nicht daneben. Was ist, wenn ich das fertige Objekt auf den Kopf stelle? Mußdann die Forderung immer noch erfullt sein?

Um solche Unklarheiten auszuschließen, werden wir bei den Sprachen ganz formal vorgehen.Wir werden Spielgregeln in Form von Grammatiken zum Aufbau von Sprachen angeben.Mit diesen Spielregeln konnen dann nur noch Worte aus einer bestimmten Sprache erzeugt(abgeleitet) werden.

Hier stellen sich sofort einige fur den Informatiker sehr wichtige und interessante Fragen:

� Laßt sich jede formale Sprache durch eine Grammatik beschreiben?

� Wenn ich eine Grammatik G habe, die eine Sprache L definiert, wie kann ich erkennen,ob ein Wort zu dieser Sprache gehort oder nicht?

� Etwas konkreter: Ist es moglich, fur eine konkrete Programmiersprache L in endlicherZeit zu entscheiden, ob ein vorgegebener Text ein Programm dieser Sprache darstelltoder nicht. Diese Aufgabe ist der Syntaxcheck des Compliers.

� Ist diese Entscheidung vielleicht sogar effizient moglich, das heißt, auch fur großeProgramme in kurzer Zeit?

� Wenn ja, wie macht man das?

� Kann man vielleicht sogar automatisch Fehler in Programmen erkennen, wie zumBeispiel Endlosschleifen?

� Kann man uberprufen, ob ein Programm korrekt ist?

Die Beantwortung dieser Fragen ist Bestandteil des Gebiets der formalen Sprachen undAutomaten. Um es vorweg zu nehmen, wir werden bis auf die erste und die letzten beidenFragen teilweise oder ganz positive Antworten liefern.

4 1 Formale Sprachen und Maschinenmodelle

Fangen wir bei den elementaren Bausteinen an.

Definition 1.1 Ein Alphabet Σ ist eine endliche nicht leere Menge von Zeichen.

Sprachen sind noch einfacher als Lego-Baukasten. Es gibt genau vier Moglichkeiten, zweiAlphabetzeichen a und b miteinander zu verknupfen, namlich aa, ab, ba, oder bb. DieseVerknupfung heißt Konkatenation und ist nicht vertauschbar. Damit kann man beliebiglange endliche Worte bauen, ahnlich wie bei den Legos.

Definition 1.2 Die Menge Σ∗ aller Worte ist wie folgt rekursiv definiert.

• Σ ⊂ Σ∗ und auch das leere Wort ε ist in Σ∗ enthalten.

• Fur jedes Wort w ∈ Σ∗ und jedes Zeichen x ∈ Σ ist auch wx ∈ Σ∗. wx ist dieZeichenkette, die entsteht, wenn man das Zeichen x an das Wort w anhangt.

Jede Teilmenge von Σ∗ wird Sprache genannt.

Beispiel 1.1

Σ = {0, 1}Σ∗ = {0, 1, ε, 00, 01, 10, 11, 001, 000, 011, 010, . . .}

Beispiel 1.2

Σ = {+,−, ·, /, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, x, y, a, b}Σ∗ = {. . . , ) +− · 567ax, . . .}

Terme = {x, y, a, b, (a), . . .}Terme ⊂ Σ∗

Die Menge aller korrekten arithmetischen Terme ist eine kleine Teilmenge von Σ∗. Ein Affe,der zufallig auf einer entsprechenden Tastatur tippt wurde viele Versuche benotigen, umeinen korrekten Term zu erzeugen. Die Wahrscheinlichkeit fur das Zustandekommen einesvorgegebenen Terms der Lange 40 ware etwa 1

240·1040 ≈ 11053 .

Definition 1.3 Sei w ∈ Σ∗ und n ∈ N0. Dann ist wn das durch n-fache Wiederholungvon w entstandene Wort. w0 ist also das leere Wort ε.

Definition 1.4 Fur eine endliche Zeichenmenge M ist M∗ die Menge aller Zeichenkettendie aus Elementen in M gebildet werden konnen. Das leere Wort gehort zu M∗ dazu.Die Menge M+ = M∗\ε enthalt dagegen nur Worte mit mindestens einem Zeichen.

1.1 Grundlagen 5

Beispiel 1.3 Sei Σ = {a, b, c}. Dann sind

∅,{aa, ab, aaa},{an|n ∈ N0} = {ε, a, aa, aaa, aaaa, . . .},{(ab)n|n ∈ N0} = {ε, ab, abab, ababab, abababab, . . .},{anbn|n ∈ N0} = {ε, ab, aabb, aaabbb, aaaabbbb, . . .}

Teilmengen von Σ∗ und somit Sprachen uber dem Alphabet Σ.

1.1.1 Unendliche Mengen

Die”kleinste” unendliche Menge ist die Menge der naturlichen Zahlen. Man konnte einfach

festlegen N := {1, 2, 3, ...}. Damit ist aber noch nicht festgelegt, was”1“,

”2“,

”3“, etc. be-

deuten soll. Daher hier die axiomatische Definition der naturlichen Zahlen.

Definition 1.5 Axiome der naturlichen Zahlen (Teil der Peano Axiome):(i) 1 ist eine naturliche Zahl(ii) jede naturliche Zahl n besitzt einen Nachfolger n+

(iii) Die Zahl 1 ist nicht Nachfolger einer naturlichen Zahl, d.h. ¬∃n ∈ N n+ = 1(iv) ∀n, m ∈ N n+ = m+ ⇒ n = m, d.h. verschiedene naturliche Zahlen haben

verschiedene Nachfolger.(v) Enthalt eine Teilmenge A der naturlichen Zahlen die Zahl 1 und mit jeder

naturlichen Zahl auch deren Nachfolger n+, so ist A = N.(A ⊂ N ∧ 1 ∈ A ∧ (n ∈ A ⇒ n+ ∈ A)) ⇒ A = N.

(v) ist das sogenannte Induktionsaxiom.Andere Formulierung: Gilt eine Aussage fur die Zahl 1 und mit jeder Zahl auch fur dessenNachfolger, so gilt sie fur alle n ∈ N.

Definition 1.6 ∅ oder {} steht fur die leere Menge. N0 = {0, 1, 2, 3, . . .}. R sei die Mengeder reellen Zahlen. Die Anzahl der Elemente einer Menge M nennt man Machtigkeitund man schreibt dafur |M |.

Beispiel: |{7, 2, 13}| = 3, |∅| = 0

Definition 1.7 Die Anzahl der Elemente einer Menge M heißt endlich, wenn es einenaturliche Zahl n gibt mit n = |M |.


Definition 1.8 Zwei Mengen M und M ′ heißen gleich machtig, wenn eine bijektiveAbbildung f : M →M ′ existiert.

Definition 1.9 Eine Menge M heißt abzahlbar, wenn sie gleich machtig wie die MangeN der naturlichen Zahlen ist. Dann lassen sich also die Elemente von M durchnumerieren.Nicht abzahlbare unendliche Mengen heißen uberabzahlbar.

Bemerkung: Jede abzahlbare Menge ist unendlich. Warum?

Satz 1.1 Die Mengen N, Z und Q sind abzahlbar. R ist uberabzahlbar.

Beweis: Wir zeigendie Abzahlbarkeit von Q, das heißt es gibt eine Bijektion Q←→ N.

Weg: Q←→ Z←→↑

Ubung

N

1 2 3 4 5 . . .

1/2 2/2 3/2 4/2 5/2

1/3 2/3 3/3 4/3 5/3

1/4 2/4 3/4 4/4 5/4...

Damit Bijektion von Q+ ←→ Z+ \ {0} analog: Bijektion von Q− ←→ Z−

dadurch Bijektion von Q←→ Z.

Satz 1.2 Die rationalen Zahlen sind dicht, d.h. zwischen je zwei rationalen Zahlen exis-tiert eine weitere rationale Zahl.

Folgerung: Zwischen zwei beliebigen rationalen Zahlen liegen unendlich viele rationaleZahlen.

Beweis: Idee: Mittelwert zweier rationaler Zahlen ist rationale Zahl.Seien a, b ∈ Q a < b. Als Ubungsaufgabe zu zeigen: a < a+b

2< b und a+b

2ist rational!

1.2 Grammatiken 7

1.1.2 Machtigkeit von Sprachen

Lemma 1.1 Fur jedes endliche Alphabet Σ ist Σ∗ abzahlbar. Die Menge aller Sprachenuber Σ ist uberabzahlbar.

Beweis: als Ubung

Die interessanten Sprachen sind unendlich. Zum Beispiel sind alle Programmiersprachenunendlich, denn wir wollen nicht die Lange von Programmen beschranken.

1.2 Grammatiken

Besonders interessant sind strukturierte Sprachen. Eine Sammlung von zufallig erzeugtenWortern ist fur die meisten Anwendungen nicht sehr hilfreich. “Struktur” heißt hier, dasssich die Sprache endlich beschreiben laßt. Wir werden Grammatiken verwenden um Spra-chen zu beschreiben.

Aus dem Sprachunterricht in der Schule ist die Grammatik der deutschen Sprache bekannt.Ein Satz der deutschen Sprache kann zum Beispiel bestehen aus <Subjekt> <Pradikat><Objekt> und <Subjekt> wiederum kann ersetzt werden durch <Artikel><Substantiv>.Damit ist also Die Studentin spielt Schach ein wohlgeformter Satz entsprechend der einfa-chen angegebenen Grammatik. Jede Programmiersprache besitzt eine Grammatik.

Beispiel 1.4 Die (unendliche) Menge der arithmetischen Terme wie zum Beispiel x · (x +a · (b− 12)) laßt sich durch folgende Regelgrammatik charakterisieren:

<Term> → <Term> + <Term><Term> → <Term> − <Term><Term> → <Term> / <Term><Term> → <Term> · <Term><Term> → (<Term>)<Term> → <Var><Term> → <Konst><Var> → x | y<Konst> → a | b | <Zahl><Zahl> → <Zahl><Ziffer> | <Ziffer><Ziffer> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Hier steht das Zeichen | fur “oder”, das heißt, eine Regel S → u | v steht fur die zwei RegelnS → u und S → v.


Definition 1.10 Eine Grammatik ist ein 4-Tupel

G = (V, Σ, P, S)

mit

• V als endliche nichtleere Menge der Variablen.

• Σ als Menge der Konstanten oder Terminalalphabet und V ∩ Σ = ∅.• P ⊂ (V ∪ Σ)+ × (V ∪ Σ)∗ als endliche Menge der Produktionsregeln.

• S ∈ V ist die Startvariable.

Definition 1.11 Die in Beispiel 1.4 und im Folgenden verwendete Art der Darstellungvon Grammatikregeln wird nach ihren Erfindern Backus-Naur-Form oder kurz BNFgenannt.

Beispiel 1.5 Mit

G = ( {<Term>,<Var>,<Konst>,<Zahl>,<Ziffer>},{x, y, a, b, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, (, ), +,−, ·, /},P, <Term>)

und P als Menge der Regeln aus Beispiel 1.4 ergibt sich also eine Grammatik mit denangegebenen Variablen, Konstanten und <Term> als Startsymbol.

Durch sukzessives Anwenden einer der Regeln aus P beginnend mit dem Startsymbol kann

1.2 Grammatiken 9

man den obigen Term x · (x + a · (b− 12)) ableiten:

<Term> ⇒ <Term> · <Term>

⇒ <Var> · <Term>

⇒ x· <Term>

⇒ x · (<Term>)

⇒ x · (<Term> + <Term>)

⇒ x · (<Var> + <Term>)

⇒ x · (x+ <Term>)

⇒ x · (x+ <Term> · <Term>)

⇒ x · (x+ <Konst> · <Term>)

⇒ x · (x + a· <Term>)

⇒ x · (x + a · (<Term>))

⇒ x · (x + a · (<Term> − <Term>))

⇒ x · (x + a · (<Konst> − <Term>))

⇒ x · (x + a · (b− <Term>))

⇒ x · (x + a · (b− <Konst>))

⇒ x · (x + a · (b− <Zahl>))

⇒ x · (x + a · (b− <Zahl><Ziffer>))

⇒ x · (x + a · (b− <Ziffer><Ziffer>))

⇒ x · (x + a · (b− 1 <Ziffer>))

⇒ x · (x + a · (b− 12))


Eine aquivalente Darstellung von Regelgrammatiken in grafischer Form bieten die Synta-xdiagramme, die wir hier nicht formal einfuhren. Ein Beispiel soll genugen:

Beispiel 1.6 Syntaxdiagramm fur Terme

Term + Term

Term Term

Term Term

Term Term

Term )

x

y

Ziffer

Term:

/

*

_

(

Var

Var:

a

b

Zahl

Konst

Konst:

Zahl: Ziffer:

0 1 2 3 4 5 6 7 8 9

Definition 1.12 Eine Folge von Wortern (w0, w1, . . . , wn) mit w0 = S und wn ∈ Σ∗

heißt Ableitung von wn, falls fur i ≥ 1 jedes der Worter wi aus wi−1 entstanden istdurch Anwendung einer Regel aus P auf ein Teilwort von wi−1. Fur einen Teilschrittschreibt man wi−1 ⇒ wi. Ist ein Wort w durch einen oder mehrere Teilschritte aus uableitbar, so schreibt man u⇒∗ w.

Obige Grammatik erzeugt die (unendliche) Menge der Terme als Teilmenge von Σ∗. Allge-mein definiert man

Definition 1.13 Die durch G erzeugte bzw. definierte Sprache ist

L(G) = {w ∈ Σ∗ | S ⇒∗ w}.

Fur kontextfreie Sprachen erhalt man eine einfachere Darstellung der moglichen Ableitun-gen eines Wortes mit Hilfe von Syntaxbaumen.

Beispiel 1.7 Der Syntaxbaum zur Ableitung aus Beispiel 1.5 hat folgende Gestalt:

1.3 Chomsky-Hierarchie 11

x

<Var>

<Term> ·

(

x

<Var>

<Term> +

a

<Konst>

<Term> ·

(

b

<Konst>

<Term> −

1

<Ziffer>

<Zahl>

2

<Ziffer>

��

eee

<Zahl>

<Konst>

<Term>

!!!!!!��

bbbb

<Term> )

��

XXXXXXXXX

<Term>

((((((((((((

��

QQ

Q

<Term>

(((((((((((((((

((((((((((((

bbbb

<Term> )

((((((((((((((((((

hhhhhhhhhhhhhhhhhh

<Term>

(((((((((((((((((((((

((((((((((((((((((

QQ

Q

<Term>

Definition 1.14 Eine Grammatik G heißt mehrdeutig, wenn es zu einem Wort ω ∈L(G) mehrere verschiedene Syntaxbaume gibt. Sie heisst eindeutig, wenn es nur einenSyntaxbaum gibt.

Wir werden nun die Grammatiken formaler Sprachen einteilen in verschiedene Klassen,die sogenannte Chomsky-Hierarchie mit dem Ziel, zu verstehen, wie sich die Eigenschaftender zugehorigen Sprachen verandern, wenn, ausgehend von den einfachsten (regularen)Grammatiken, immer komplexere Regeln erlaubt sind.

1.3 Chomsky-Hierarchie


Definition 1.15 Jede Grammatik G = (V, Σ, P, S) entsprechend Definition 1.10 ist vomTyp 0. Die Menge der Typ-0-Grammatiken ist also gleich der Menge aller Grammatiken.

Typ Bezeichnung erlaubte Regeltypen, (w ∈ (V ∪ Σ)+, u ∈ (V ∪ Σ)∗)0 Grammatik w → u.1 kontextsensitiv w → u mit |w| ≤ |u|.2 kontextfrei A → u, A → ε, mit A ∈ V , d.h. auf der linken Seite aller Regeln

kommt genau eine Variable vor.3 regular A→ a, A→ aB, A→ ε, d.h. auf der rechten Seite der Regeln steht

entweder ein Terminalsymbol oder ein Terminalsymbol gefolgt voneiner Variablen.

Eine Sprache ist vom Typ t, wenn es eine Grammatik vom Typ t gibt mit L(G) = L.

Beispiel 1.8 Die Sprache aus Beispiel 1.4 ist offensichtlich eine kontextfreie Grammatik,das heißt sie ist vom Typ 2. Sie ist aber keine Typ-3-Grammatik. (Warum?)

Beispiel 1.9 Die Sprache {anbn|n ∈ N} ist kontextfrei und laßt sich durch die GrammatikG = ({S}, {a, b}, P, S) beschreiben mit

P = { S → aSb,

S → ab }.

Diese Sprache ist nicht regular.

Beispiel 1.10 Die Sprache {anbm|n ∈ N, m ∈ N} ist regular und laßt sich durch dieGrammatik G = ({S, T}, {a, b}, P, S) beschreiben mit

P = { S → aS,

S → aT,

T → bT,

T → b }.

Die Chomsky-Hierarchie der verschiedenen Sprachklassen ist in folgendem Mengendia-gramm dargestellt:

1.3 Chomsky-Hierarchie 13

alle Sprachenuberabzahlbar weil P (Σ∗)

durch Grammatiken beschreibbare Sprachen → Typ 0abzahlbar

Typ 1

Typ 2

Typ 3

alle endlichen Sprachen

Beispiel 1.11

Σ = {a, b}G1 = ({S}, Σ, P, S)

P = {S → aS, S → bS, S → ε}

Offenbar laßt sich aus dieser Grammatik jedes Wort w ∈ Σ∗ ableiten, also gilt L(G1) = Σ∗.Diese Aussage laßt sich wie folgt verallgemeinern.

Satz 1.3 Sei Σ = {c1, . . . , cn}. Dann ist Σ∗ eine Typ-3-Sprache und jede endliche Teilmen-ge von Σ∗ ist vom Typ 3.

Beweis:

1. Teil:

Σ = {c1, . . . , cn}G1 = ({S}, Σ, P, S)

P = {S → c1S, S → c2S, . . . , S → cnS, S → ε}es folgt:

L(G1) = Σ∗

Weil alle Regeln aus P Typ 3 - Regeln sind ist Σ∗ vom Typ 3.

2. Teil:


Sei die endliche Sprache L = {w1, w2, . . . , wm} gegeben. Die Grammatikregeln fur das Wortwi = ci1ci2 . . . cili sind:

Pi = {S → ci1Si1, Si1 → ci2Si2, . . . , Sili → ε}G = (V, Σ, P, S)

Σ = ∪mi=1 ∪

lij=1 {cij}

V = {S, S11, . . . , S1l1 , . . . , Sm1, . . . , Smlm}P = ∪m

i=1Pi

1.4 Endliche Automaten

Nun kennen wir einige regulare Sprachen und deren Regelgrammatik. Mit Hilfe der Gram-matik lassen sich alle Worte der Sprache erzeugen. Wir stellen uns die Frage, ob es einemoglichst einfache und effiziente Rechenmaschine gibt, mit der man fur ein beliebiges Wortw entscheiden kann, ob dieses zu einer vorgegebenen regularen Sprache gehort.

Definition 1.16 Die Aufgabe, zu entscheiden, ob ein Wort w zu einer Sprache L gehort,heißt Wortproblem.

Grammatikerzeugt−→ Sprache

erkennt←− Automat

Das Wortproblem fur regulare Sprachen kann durch endliche Automaten effizient ge-lost werden. Anschaulich ist ein endlicher Automat ein Rechenelement, welches auf einemEingabeband beginnend mit dem ersten Zeichen das eingegebene Wort Zeichen fur Zeichenliest.

H A L L O

Z Zustand

Lesekopf

Hierbei kann er seinen internen Zustand entsprechend von Regeln abhangig vom Eingabe-zeichen wechseln. Die Zahl der Zustande ist endlich. Erreicht der Automat nach Lesen desletzten Zeichens einen Endzustand, so hat er das Wort erkannt. Formal wird der Automatwie folgt definiert:

1.4 Endliche Automaten 15

Definition 1.17 Ein endlicher Automat M besteht aus einem 5-, bzw. 7-Tupel

M = (Z, Σ, δ, z0, E)

bzw.M = (Z, Σ, δ, z0, E, γ, Θ)

mit

Z : endliche Zustandsmenge

Σ : endliches Eingabealphabet, Σ ∩ Z = φ

δ : Z × Σ→ P(Z), die Zustandsubergangsfunktion

z0 : Startzustand

E : Menge der Endzustande

γ : Z × Σ→ Θ, die Ausgabefunktion

Θ : Ausgabealphabet

Definition 1.18 Ein Wort w = w1 . . . wn mit wi ∈ Σ wird akzeptiert von demendlichen Automaten M genau dann wenn M gestartet im Startzustand auf w1 nachn Anwendungen der Funktion δ, d.h. nach Lesen von wn, einen Endzustand z ∈ Σerreichen kann.

Die von M akzeptierte (erkannte) Sprache L(M) ist

L(M) = {w ∈ Σ∗ |M akzeptiert w}

Satz 1.4 Eine Sprache L wird von einem endlichen Automaten genau dann erkannt, wennsie regular (Typ 3) ist.

Beispiel 1.12 Die regulare Sprache L = {anbm | n ∈ N, m ∈ N} wird erzeugt durchdie Regelmenge

P = {S → aS, S → aT, T → bT, T → b}

Die Zustandsubergangsfunktion δ des zugehorigen Automaten M = ({S, T, e}, {a, b}, δ, S, {e})ist gegeben durch die Zustandsubergangstabelle

δ S T ea {S, T}b {T, e}

Man beachte, dass die Zustandsubergangsfunktion δ nicht eindeutig ist, denn zum Beispielkann der Automat nach Lesen eines a im Zustand S nach S oder nach T ubergehen. Dieszeichnet den nichtdeterministischen Automaten aus.

Der zugehorige Zustandsgraph ist


S T

a

a

b

be

Beispiel 1.13 Es soll ein Getrankeautomat mit Hilfe eines endlichen Automaten program-miert werden. Der Automat kann mit bis zu 4 Dosen Mineralwasser gefullt werden. Wenneine 1-Euro-Munze eingegeben wird, soll er eine Dose Wasser ausgeben. Bei Eingabe eineranderen Munze soll er die eingegebene Munze wieder ausgeben, aber kein Getrank. Wennder Automat leer ist soll er anhalten und per Funk den Service benachrichtigen.

Ein endlicher Automaten (mit Ausgabe) fur diese Aufgabe ist

({z0, z1, z2, z3, z4}, {e, f, m}, δ, z0, {z0}, γ, {e, f, m})

wobei δ und γ gegeben sind durch

δ, γ z0 z1 z2 z3 z4

m z1, ε z2, ε z3, ε z4, εe z0, e z0, m z1, m z2, m z3, mf z0, f z1, f z2, f z3, f z4, f

Das Zustandsdiagramm zu diesem Automaten sieht so aus:

Dieser Automat akzeptiert alle Eingabesequenzen (Worte), die zum leeren Automaten (d.h.zu z0) fuhren.

Definition 1.19 Beim nichtdeterministischen endlichen Automaten (NFA) sind (im Ge-gensatz zum deterministischen endlichen Automaten (DFA)) fur jeden Zustand Z undEingabezeichen a mehrere Regeln

z, a→ z1

...

z, a→ zn

erlaubt.

Bemerkung:Aus der Zustandsubergangsfunktion δ wird eine Relation.

Beispiel 1.14 An der Sprache L = {anbm|n ∈ N, m ∈ N} erkennt man schon, wie dieRegelgrammatik in einfacher Weise in einen nichtdeterministischen Automaten ubersetztwerden kann:

1.5 Regulare Ausdrucke 17

Regelgrammatik AutomatP = {S → aS δ = {S, a → S

S → aT S, a → TT → bT T, b → TT → b } T, b → E }

Hier stellt sich die Frage, ob es vielleicht auch einen deterministischen Automaten gibt, derdiese Sprache erkennt. Allgemein lautet die Frage: Sind nichtdeterministische Automatenmachtiger ist als deterministische. Der folgende Satz beantwortet beide Fragen.

Satz 1.5 NFAs und DFAs sind gleich machtig, d.h. zu jedem NFA gibt es einen DFA, derdie gleiche Sprache erkennt.

1.5 Regulare Ausdrucke

Regulare Ausdrucke dienen wie regulare Grammatiken der Beschreibung von Typ-3-Sprachen.

Definition 1.20 Regulare Ausdrucke zum Alphabet Σ sind:

1.) ∅ = {}

2.) ε

3.) a, falls a ∈ Σ

4.) sind α, β regulare Ausdrucke, so auch αβ, α|β und α∗

hierbei steht α|β fur α oder β, α∗ fur beliebig viele Wiederholungen von α (auch 0Wiederholungen).

Beispiel 1.15 aa∗bb∗ beschreibt {anbm/n ∈ N, m ∈ N}. Fur aa∗ schreibt man kurzer a+.Der Operator + steht also fur beliebig viele Wiederholungen, aber mindestens eine.

Beispiel 1.16 Sei Σ = {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Der Ausdruck 0\.(0|1|2|3|4|5|6|7|8|9)+beschreibt die Menge aller Dezimalzahlen mit 0 vor dem Dezimalpunkt.

Da wir im Folgenden das Werkzeug Lex bzw. Flex vorstellen werden, wird die Definitionder regularen Ausdrucke gekurzt entnommen aus der Linux-Manual-Page zu FLex. DieRangfolge der Operatoren entspricht deren Prioritat.


x match the character ’x’. any character (byte) except newline[xyz] a "character class"; in this case, the pattern

matches either an ’x’, a ’y’, or a ’z’[abj-oZ] a "character class" with a range in it; matches

an ’a’, a ’b’, any letter from ’j’ through ’o’,or a ’Z’

[^A-Z] a "negated character class", i.e., any characterbut those in the class. In this case, anycharacter EXCEPT an uppercase letter.

[^A-Z\n] any character EXCEPT an uppercase letter ora newline

r* zero or more r’s, where r is any regular expressionr+ one or more r’sr? zero or one r’s (that is, "an optional r")r{2,5} anywhere from two to five r’sr{2,} two or more r’sr{4} exactly 4 r’s{name} the expansion of the "name" definition

(see above)"[xyz]\"foo"

the literal string: [xyz]"foo\X if X is an ’a’, ’b’, ’f’, ’n’, ’r’, ’t’, or ’v’,

then the ANSI-C interpretation of \x.Otherwise, a literal ’X’ (used to escapeoperators such as ’*’)

\0 a NUL character (ASCII code 0)\123 the character with octal value 123\x2a the character with hexadecimal value 2a(r) match an r; parentheses are used to override

precedence (see below)rs the regular expression r followed by the

regular expression s; called "concatenation"r|s either an r or an s^r an r, but only at the beginning of a line (i.e.,

which just starting to scan, or right after anewline has been scanned).

r$ an r, but only at the end of a line (i.e., justbefore a newline).

Mit dieser erweiterten Notation fur regulare Ausdrucke lassen sich Dezimalzahlen (sie-he Beispiel 1.16) einfacher beschreiben mit 0\.[0123456789]+ oder noch einfacher durch0\.[0-9]+.Bevor wir mit der praktischen Anwendung von regularen Ausdrucken fortfahren noch einwichiger Satz.

Satz 1.6 Jede regulare Sprache ist durch einen regularen Ausdruck beschreibbar. Umge-kehrt definiert jeder regulare Ausdruck eine regulare Sprache.

1.6 Der Lexical Analyzer Lex 19

1.6 Der Lexical Analyzer Lex

Lex, bzw. FLEX ist ein sogenannter Lexical Analyzer. Er kann dazu verwendet werden,fur regulare Sprachen das Wortproblem zu losen, das heisst, zu entscheiden, ob ein vorge-gebenes Wort zu einer Sprache L gehort. Lex kann daneben sogar noch erkannte Worterersetzen entsprechend definierten Regeln.

Das Ersetzen von Ausdrucken der Form

Tel.: 0751/501-721

durch Ausdrucke der Form

Phone: ++49-751-501-721

kann durch folgendes Lex-Programm erfolgen.

Die Datei tel.x:

%option noyywrap%%Tel\.?:[ \t]+0 printf("Phone: ++49-");[0-9](\/|-)[0-9] printf("%c-%c", yytext[0],yytext[2]);\n printf("\n");

Anwendung des fertigen Programms tel liefert:

> tel

Tel.: 0751/501-9721

Phone: ++49-751-501-9721

Tel.: 075qt1/501-9721

Phone: ++49-75qt1-501-9721

quit

quit

^D

Aufruf von Lex mit Quelldatei tel.x:

flex -otel.c tel.x

cc -lfl tel.c -o tel

tel

der generelle Aufbau eines Lex-Programms (und auch eines Yacc-Programms) ist:

Definitionen%%

Regeln%%

Funktionen


1.7 Yacc: Yet Another Compiler Compiler

Yacc ist ein Programmgenerator, der aus einer kontextfreien Grammatik ein Programmgeneriert, das die Korrektheit der eingegebenen Worte pruft, das heisst das Wortproblementscheidet. Yacc wird hauptsachlich dazu verwendet, Parser fur Programmiersprachenautomatisch zu erzeugen. Er kann also nicht nur die Syntax von Programmiersprachenchecken, sondern auch Code generieren. Dies fuhrt jedoch hier zu weit.

1.7.1 Ein Beispiel mit Lex und Yacc

Die Datei term.x

#include "y.tab.h"%%$ return(yytext[0]);$ return(yytext[0]);[\+\-\*\/] return(OP);[ \t]+ ;[a-zA-Z][a-zA-Z0-9_]* return(BEZ);[0-9]+ return(INTEGER);[0-9]+\.[0-9]+ return(GLEITPKTZ);\n return(’\0’);

Die Bison-Eingabedatei term.y

%token BEZ OP INTEGER GLEITPKTZ%%term : INTEGER

| GLEITPKTZ| BEZ| term OP term| ’(’ term ’)’| error {printf("Term nicht wohlgeformt!\n");}

%%yyerror (s) /* Called by yyparse on error */char *s;{printf ("%s\n", s);

}

#include "lex.yy.c"

main(){/* yydebug = 1;*/yyparse();

}

1.8 Kellerautomaten 21

Die Datei makefile

term: lex.yy.c term.tab.ccc term.tab.c -lfl -o term

term.tab.c: term.ybison term.y

lex.yy.c: term.xflex term.x

Ablauf und Zusammenspiel von Lex, Yacc und CC:

1.8 Kellerautomaten

Wir starten mit einem Beispiel an dem man erkennt, dass schon recht einfache Sprachenvon einem endlichen Automaten nicht erkannt werden konnen.

Beispiel 1.17

L = {anbn|nεN}

Grammatik fur L:

P = {S → aSb, S → ab}

L ist eine Typ-2-Sprache. Daher gibt es keine regulare Grammatik fur L und auch keinenendlichen Automaten, der L erkennt.

Beispiel 1.18 Beschrankt man allerdings die Zahl n der a-s und b-s, so gibt es einenendlichen Automaten, der die Sprache erkennt. Sei also

L′ = {anbn|n = 1, . . . , 100}.

Diese Sprache wird erkannt von einem Automaten mit Endzustand E und folgenden Zu-standsubergangen


A0, a→ A1 B0, b→ EA1, a→ A2 A1, b→ B1 B1, b→ B0

A2, a→ A3 A2, b→ B2 B2, b→ B1

. . . . . . . . .A98, a→ A99 A99, b→ B99 B99, b→ B98

Definition 1.21 Ein Kellerautomat K besteht aus einem 6-Tupel

K = (Z, Σ, Γ, δ, z0, #)

mit


Σ : endliches Eingabealphabet, Σ ∩ Z = ∅Γ : endliches Kelleralphabet, Σ ∩ Γ = ∅δ : Z × (Σ ∪ {ε})× Γ→ Pe(Z × Γ∗), die Zustandsubergangsfunktion1

z0 ∈ Z : Startzustand

# ∈ Γ : unterstes Kellerzeichen

Beispiel 1.19 Kellerautomat K fur L = {anbn|n ∈ N}

K = {{z0, z1}, {a, b}, {A, #}, δ, z0, #}

δ = {z0, a, # → z0, A#;

z0, a, A → z0, AA;

z0, b, A → z1, ε;

z1, b, A → z1, ε;

z1, ε, # → z1, ε}

Folgende Sequenz von Konfigurationen veranschaulicht die Arbeit von K:

a a b b↑z0

#

a a b b↑z0 A

#

a a b b↑z0

AA#

1.8 Kellerautomaten 23

a a b b↑z1 A

#

a a b b↑z1

#

a a b b↑z1

L = {anbncm|n ∈ N, m ∈ N0}

δ′ = δ ∪ {z1, c, #→ z1, #}

Beispiel 1.20 Palindrome sind Worte, die in der Mitte gespiegelt sind. Wir betrachtennun die Sprache aller Palindrome uber dem Alphabet {a, b}, wobei die Mitte des Wortesjeweils durch ein $-Zeichen markiert ist. Sei also

Σ = {a, b, $} und L = {a1 . . . an$an . . . a1|ai ∈ {a, b}, n ∈ N0}

Die Sprache wird erzeugt durch die Typ-2-Grammatik G = (V, Σ, P, S) mit

P = {S → $|aSa|bSb}

L ist keine Typ 3 Sprache, denn wie oben gezeigt gibt es keinen endlichen Automaten zudieser Sprache. Folgender deterministischer Kellerautomat erkennt L:

Eingabezeichen s0 s1

Kellerzeichena, # s0, A#b, # s0, B#$, # s1, #a, A s0, AA s1, εa, B s0, ABb, A s0, BAb, B s0, BB s1, ε$, A s1, A$, B s1, Bε, # s1, ε

Beispiel 1.21 Lassen wir die Mittenmarkierung weg, so ergibt sich

Σ = {a, b} und L = {a1 . . . anan . . . a1|ai ∈ Σ, n ∈ N0}

mit der Grammatik

P = {S → aSa|bSb|ε}.

Hier kann man nun die Mitte des Wortes nicht mehr in einem deterministischen Durchlauferkennen. Daher ist ein nichtdeterministischer Kellerautomat gefordert:


Eingabezeichen, s0 s1

Kellerzeichena, # s0, A#; s1, A#b, # s0, B#; s1, B#a, A s0, AA; s1, AA s1, εa, B s0AB; s1ABb, A s0, BA; s1BAb, B s0, BB; s1, BB s1, εε, # s1, ε s1, ε

Die Semantik des Erkennens eines Wortes durch einen deterministischen Kellerautomatendefinieren wir wie folgt:

Definition 1.22 Ein (nichtdeterministischer) Kellerautomat K erkennt, bzw. akzep-tiert ein Wort w = w1 . . . wn genau dann, wenn es eine Folge von Zustandsubergangengibt, so dass nach Lesen von wn der Keller ganz leer ist. Hierbei muß K gestartet werdenauf w1.

An diesem Beispiel erkennt man, dass nichtdeterministische Kellerautomaten machtigersind als deterministische, d.h. es gibt Sprachen, zum Beispiel die Palindrome, die vonnichtdeterministischen Kellerautomaten erkannt werden, aber nicht von deterministischen.

Satz 1.7 Nichtdeterministische Kellerautomaten erkennen genau die Menge der kontext-freien Sprachen (Chomsky Typ 2). Deterministische Kellerautomaten erkennen genau dieMenge der deterministisch kontextfreien Sprachen. Diese Sprachen werden von LR(k)-Grammatiken erzeugt und liegen in der Chomsky-Hierarchie zwischen Typ 2 und 3.

1.9 Turingmaschinen

Eine der vielen großen Erfindungen des genialen britischen Mathematikers Alan Turing(≈ 1940) war die Definition eines Modells fur eine universelle Rechenmaschine, welche alleFunktionen berechnen kann, die wir uns intuitiv als berechenbar vorstellen. Die sogenannteTuringmaschine besitzt endliche viele Zustande und arbeitet auf einem beidseitig unend-lichen Band. Ihre Machtigkeit erhalt sie durch die Moglichkeit Zeichen auf dem Band zuuberschreiben sowie den Schreib-Lesekopf nach rechts oder links zu bewegen.

Beispiel 1.22 Turingmaschine T , die eine Eingabe x ∈ {0, 1}∗ als Binarzahl interpretiertund 1 hinzuaddiert. Ein leeres Bandfeld bezeichnen wir im Folgenden mit t.

T = ({z0, z1, z2, ze}, {0, 1}, {0, 1,t}, δ, z0,t, {ze})

1.9 Turingmaschinen 25

z0, 0 → z0, 0, R

z0, 1 → z0, 1, R

z0,t → z1,t, L

z1, 0 → z2, 1, L

z1, 1 → z1, 0, L

z1,t → ze, 1, N

z2, 0 → z2, 0, L

z2, 1 → z2, 1, L

z2,t → ze,t, R

Die Maschine bewegt sich zuerst nach rechts bis zum Ende der Binarzahl. Dann erfolgt dieeigentliche Addition im Zustand z1 mit Bewegung nach links. Bei der ersten null ist dieAddition abgeschlossen und im Zustand z2 lauft T zum Anfang der Zahl, wo sie terminiert.

Definition 1.23 Ein Turingmaschine besteht aus einem 7-Tupel

T = (Z, Σ, Γ, δ, z0,t, E)

mit


Σ : endliches Eingabealphabet, Σ ∩ Z = ∅Γ : endliches Arbeitsalphabet, mit Σ ⊂ Γ

δ : Z × Γ→ Z × Γ× {L, R, N},die Zustandsubergangsfunktion bei deterministischen Turingmaschinen

δ : Z × Γ→ P(Z × Γ× {L, R, N}),die Zustandsubergangsfunktion bei nichtdeterministischen Turingmaschinen

z0 : Startzustand, z0 ∈ Z

t : Das Blank (Leerzeichen), wobei t ∈ Γ− Σ

E : Menge der Endzustande mit E ⊆ Z

Definition 1.24 Ein Wort w = w1 . . . wn wird von einer Turingmaschine T akzeptiert,wenn sie, gestartet auf w1 in einem Endzustand halt.

L(T ) = {w ε Σ∗|T akzeptiert w}

Satz 1.8 Turingmaschinen akzeptieren genau die Typ-0-Sprachen.


Man konnte aufgrund dieses Satzes verleitet sein, zu glauben, dass Turingmaschinen dasWortproblem (Definition 1.16) losen. Dies ist aber falsch. Man vergleiche hierzu zum Bei-spiel den kleinen aber subtilen Unterschied in den Definitionen 1.22 und 1.24. Der Kellerau-tomat akzeptiert ein Wort “genau dann wenn . . . ”, die Turingmaschine hingegen akzeptiertein Wort “wenn . . . ”. Uber den Fall, dass die Turingmaschine nicht in einem Endzustandhalt, macht die Definition keine Aussage. Warum?

Beispiel 1.23 Besonders einfach sind Turingmaschinen, die unendlich viele 1-en schreiben:

z0,t → z0, 1, R

Viel schwieriger ist es, moglichst viele, aber endlich viele Einsen zu schreiben.

1.9.1 Fleißige Biber

Die Turingmaschine ist extrem ineffektiv bei der Bearbeitung von konkreten Problemen.Fur die Theorie hat sie aber große Bedeutung. So kann mit ihrer Hilfe zum Beispiel dasHalteproblem, ein fur die Informatik sehr wichttiges Problem (leider negativ) beantwortetwerden.

Der ungarische Mathematiker Tibor Rado definierte 1962 das busy-beaver-Problem:

Definition 1.25 Busy- Beaver- Problem:Gesucht ist eine deterministische Turingmaschine mit dem Arbeitsalphabet {1,t} undeiner vorgegebenen Anzahl von Zustanden. Das Turingband ist leer. Wie viele Zeichenkann sie maximal schreiben?

Bemerkung: Es ist kein Problem, eine Turingmaschine zu entwerfen, die unendliche vieleZeichen schreibt (s.o.). Aber die Turingmaschine soll ja irgendwann anhalten. Das machtdas Problem so schwierig. Bei der Anzahl der Zustande der fleißigen Biber werden dieEndzustande nicht mitgezahlt.

Beispiel 1.24 Dieser Busy Beaver mit 2 Zustanden schreibt 4 Einsen:

z0,t → z1, 1, R

z0, 1 → z1, 1, L

z1,t → z0, 1, L

z1, 1 → ze, 1, R

Beispiel 1.25 Busy Beaver mit 3 Zustanden, der 6 Einsen schreibt:

t 1z0 z1, 1, R z2, 1, Lz1 z2, 1, R ze, 1, Nz2 z0, 1, L z1,t, L

1.9 Turingmaschinen 27

Beispiel 1.26 Noch ein fleißiger Biber mit 3 Zustanden:

z0,t → z1, 1, R

z0, 1 → z2, 1, L

z1,t → z0, 1, L

z1, 1 → z1, 1, R

z2,t → z1, 1, L

z2, 1 → ze, 1, N

Der gleiche Biber als Automat dargestellt:

Man kann zeigen, dass eine Turingmaschine mit einem Zustand maximal ein Zeichen schrei-ben kann, eine mit zwei Zustanden maximal vier Zeichen, eine mit drei Zustanden maximalsechs Zeichen, eine mit vier Zustanden maximal dreizehn Zeichen.

Es gibt viele Turingmaschinen

Satz 1.9 Fur die Zahl T (n) der Turingmaschinen mit Arbeitsalphabet t, 1 und n Zustan-den (ohne Endzustand) gilt

T (n) = (6n + 7)2n.

Beweis: Wir betrachten Regeln der Form

s, z −→ s′, z′, m

und erkennen, dass es bei n Zustanden 2n linke Seiten gibt. Fur jede mogliche linke Seitegibt es auf der rechten Seite n + 1 Zustande s′ (inkl. Endzustand), 2 verschiedene Zeichenz′ und 3 Bewegungen (R,L,N). Dies ergibt 6(n + 1) rechte Seiten fur jede linke Seite. Daman zu jeder linken Seite aber auch gar keine Regel angeben kann, gibt es insgesamt zujeder linken Seite

6(n + 1) + 1 = 6n + 7


Moglichkeiten. Bei 2n linken Seiten ergeben sich insgesamt

(6n + 7)2n

Turingmaschinen fur das Arbeitsalphabet t, 1. 2

Folgende Tabelle aus [18] listet einige aktuelle bekannte Ergebnisse uber fleißige Biber auf.Hier ist n die Zahl der Zustande (ohne Endzustand), Σ(n) die maximale Zahl geschriebenerEinsen. Interessant ist offenbar auch folgende Frage: Welche Turingmaschine mit n Zustan-den - ohne Endzustand - macht moglichst viele Arbeitschritte, stoppt dann und hinterlasstein leeres Band? Als S(n) bezeichnen wir die maximal mogliche Zahl von Rechenschrittensolch einer Maschine mit n Zustanden.

n T (n) Σ(n) S(n) Quelle1 169 1 1 Lin und Rado2 130321 4 6 Lin und Rado3 ≈ 2.4 · 108 6 21 Lin und Rado4 ≈ 8.5 · 1011 13 107 Brady5 ≈ 4.8 · 1015 ≥ 4098 ≥ 47, 176, 870 Marxen und Buntrock6 ≈ 4.0 · 1019 > 4.6 · 101439 > 2.5 · 102879 T.J. und S. Ligocki

Die Funktion Σ(n), die angibt, wie gross die maximale Zahl von Zeichen ist, die eineTuringmaschine mit n Zustanden (ohne Endzustand) ausgeben kann, ist zwar wohldefiniert,aber nicht durch eine Turingmaschine und somit uberhaupt nicht berechenbar! Das Gleichegilt fur die Funktion S(n). Beides werden wir im nachsten Kapitel zeigen.

1.10 Zusammenfassung zu Sprachen undMaschinenmodellen

Vergleich von Sprachtypen und Maschinenmodellen:

Chomsky Beschreibung Maschinen-Modell Komplexitat des-Typ Wortproblems

0 Regelgrammatiken Turingmaschine halbentscheidbar1 kontextsensitive linear beschrankter O(an) (exponentiell)

Grammatik Automat (TM)2 kontextfreie Grammatik Kellerautomat O(n3)

(nichtdeterminist.)3 regulare Grammatiken / endlicher Automat Θ(n)

regulare Ausdrucke

Satz 1.10 Church’sche These: Die Menge, der durch Turingmaschinen berechenbarenFunktionen entspricht genau der Menge aller intuitiv berechenbaren Funktionen.

1.11 Ubungen 29

Die Church’sche These ist kein Satz im strengen Sinne, denn der Begriff intuitiv widersetztsich einem Beweis.

Satz 1.11 Die Turingmaschine ist gleich machtig wie der von-Neumann-Rechner, dasheißt, dass jedes Problem, das ein von-Neumann-Rechner lost auch von einer Turingma-schine gelost werden kann und umgekehrt.

Damit ist die Menge der Berechnungsprobleme, die von Turingmaschinen gelost werdenkonnen gleich der Menge der Berechnungsprobleme, die mit einer “klassischen” Program-miersprache (wie zum Beispiel C) gelost werden konnen. Man nennt eine derartige Pro-grammiersprache Turing-machtig.

1.11 Ubungen

Aufgabe 1 Wieviele Teilmengen besitzt eine endliche Menge mir n Elementen? Beweis!

Aufgabe 2 Zeigen Sie, dass die Menge der reellen Zahlen R uberabzahlbar ist. (Tipp:Wenn Sie den Beweis nicht schaffen, suchen in der Bibliothek oder in meinem Analysis-1-Skript auf meiner Webseite)

Aufgabe 3 Gegeben sei die Grammatik ([9], S. 15)

G = (V, Σ, P, S) , wobei:

V = {S, B, C}Σ = {a, b, c}P = {S → aSBC, S → aBC, CB → BC,

aB → ab, bB → bb, bC → bc, cC → cc}

Konstruieren Sie eine Ableitung fur aabbcc. Welchen Chomski-Typ hat diese Grammatik?

Aufgabe 4 Geben sie eine moglichst einfache Grammatik an, die alle Zeichenketten derForm ab, abab, ababab, . . . erzeugt. Welchen Chomski-Typ hat diese Grammatik?

Aufgabe 5 Geben sie eine moglichst einfache Grammatik an, die alle Zeichenketten derForm ab, aabb, aaabbb, . . . erzeugt. Welchen Chomski-Typ hat diese Grammatik?

Aufgabe 6 Geben sie eine moglichst einfache Grammatik an, die alle Zeichenketten derForm abba, ababbaba, abababbababa, . . . erzeugt. Zeichnen Sie den Syntaxbaum fur dasWort ababbaba. Welchen Chomski-Typ hat diese Grammatik?

Aufgabe 7 Definieren Sie eine Grammatik, die einfache Programme folgender Art be-schreibt. Es gibt im Programmrumpf nur Wertzuweisungen, Terme sowie den print-Befehl

function plusplus(x,y,z)

var int u,v;


var float w;

u = x + y;

v = x * (z+y);

w = x / z;

print(u,v,w)

end

Aufgabe 8

a) Zeigen Sie, dass die Menge aller C-Programme unendlich ist.

b) Geben sie eine obere Schranke fur die Zahl der C-Programme der Lange n an.

Aufgabe 9 Gegeben sei die Grammatik G = (V, Σ, P, S) mit V = {S, A,B}, Σ = {a, b, c}und

P = { S → aA, A→ aA, B → bB,S → bA, A→ bB, B → c,

A→ c }

a) Geben Sie eine Ableitung an fur abbbbc.

b) Geben Sie alle Worte der Lange 4 der zugehorigen Sprache L = L(G) an.

c) Geben Sie einen regularen Ausdruck fur die Sprache L an.

d) Zeichnen Sie den Zustandsgraphen eines endlichen Automaten, der L akzeptiert.

e) Geben Sie den endlichen Automaten als Formel an.

f) Welchen Chomsky Typ hat diese Sprache? (Begrundung!)

Aufgabe 10 Geben Sie einen deterministischen endlichen Automaten an, der die Sprache{anbm|n ∈ N, m ∈ N} erkennt.

Aufgabe 11 Geben Sie eine Grammatik an, welche die von dem Getrankeautomaten ausBeispiel ?? erkannte Sprache erzeugt.

Aufgabe 12 Geben Sie eine Grammatik an fur die Sprache L = {aibjck | i = j oder j = k}Zeigen sie daß diese Grammatik mehrdeutig ist.

Aufgabe 13 Geben Sie regulare Ausdrucke an fur

a) groß geschriebene Worte wie z.B. Hallo, aber nicht HALLO.

b) groß geschriebene Worte mit mindestens 3 und hochstens 10 Buchstaben.

c) Gleitpunktzahlen mit beliebig vielen Stellen vor dem Komma und mindestens einerStelle nach dem Komma.

d) Datumsangaben der Form 21.10.1999 oder 1.1.2000 oder 1.1.‘00 oder 21.10.‘99.Nicht erlaubt sind unzulassige Werte wie z.B. 33.44.‘99 oder 121.10.1999

1.11 Ubungen 31

Aufgabe 14

Beschreiben Sie die durch folgende regularen Ausdrucke definierten Sprachen und gebenSie Beispiele an.

a) \\(index|color|label|ref)\{[^\}]*\}

b) %.*$

c) \\section\*?\{.*\}

d) [A-Za-z0-9]+@[A-Za-z0-9]+(\.[A-Za-z0-9]+){1,6}

Aufgabe 15 Schreiben Sie ein Lex-Programm, das in einer Datei alle Datumsangabenvom Format< Tag > . < Mon > . < Jahr > in das Format < Mon > − < Tag > − < Jahr >ubersetzt. < Tag > und < Mon > sind zu verstehen wie in Aufgabe 13.

Aufgabe 16 Konstruieren Sie mit Lex und Yacc einen Parser fur die Grammatik inAufgabe 7.

Aufgabe 17 Es soll ein Getrankeautomat mit Hilfe eines endlichen Automaten program-miert werden. Der Automat kann mit bis zu 4 Dosen Mineralwasser, 4 Dosen Limo und 4Dosen Bier gefullt werden. Wenn eine 1-Euro-Munze eingegeben wird, soll er eine Dose desgewahlten Getranks ausgeben. Bei Eingabe einer anderen Munze soll er die eingegebeneMunze wieder ausgeben, aber kein Getrank. Wenn von einer Getrankesorte alle Dosen aus-gegeben sind, soll er anhalten und per Funk den Service benachrichtigen. Geben Sie einenendlichen Automaten (mit Ausgabe) fur diese Aufgabe an. Uberlegen Sie sich, wie Sie diegroße Zahl von Regeln durch wenige (Meta-) Regeln beschreiben konnen.

Aufgabe 18 Es soll eine Fußgangerampel mit Hilfe eines endlichen Automaten program-miert werden. Die Ampel hat die zwei Zustande rot und grun (aus der Sicht des Fahrzeugs).Im Zustand rot akzeptiert die Ampel Signale von der Kontaktschleife auf der Straße undschaltet dann auf Grun. Im Zustand Grun akzeptiert die Ampel Signale vom Fußganger-taster und schaltet auf Rot. Alle anderen Eingaben ignoriert der Automat.

a) Geben Sie einen endlichen Automaten fur diese Aufgabe an.

b) Zeichnen Sie ein Zustandsdiagramm zu diesem Automaten.

c) Geben Sie einen regularen Ausdruck fur diese Sprache an.

d) Geben Sie eine regulare Grammatik fur diesen Automaten an.

e) Zeigen Sie, dass diese Ampelschaltung bei geringem Verkehrsaufkommen das Mehr-heitsprinzip exakt erfullt, das heisst, das Verhaltnis aus rot- zu grun-Zustanden istgleich dem Verhaltnis aus Fußgangerzahl zu Autofahrerzahl.

Aufgabe 19

Konstruieren sie (deterministische oder nichtdeterministische) endliche Automaten fur fol-gende durch regulare Ausdrucke gegebenen Sprachen:

a) [0-9]*\.[0-9]+


b) \\section\*?\{.*\}

Aufgabe 20

a) Entwerfen sie fur das Alphabet {a,b} einen Kellerautomaten, der alle Worte derForm x1, x2, . . . xn$y1, y2, . . . ym erkennt, wobei die Zahl der a-s vor und nach dem“$”-Zeichen gleich groß sein soll.

b) Geben Sie fur diese Sprache eine BNF Grammatik an.

Aufgabe 21

a) Andern Sie den Automaten aus Aufgabe 20 so ab, daß er nur Worte erkennt, fur dien = m ist.

b) Geben Sie fur die geanderte Sprache auch eine BNF Grammatik an.

Aufgabe 22 Entwerfen Sie sie fur das Alphabet {a,(,)} einen Kellerautomaten, der genaudie korrekt geklammerten Ausdrucke erkennt.

Aufgabe 23 Gegeben sei die BNF-Grammatik G = ({S, T, Z}, {a, [, ]}, P, T ) mit

P = { T → [S[STS]S] | εS → ZS |Z | εZ → a }

a) Geben Sie eine Linksableitung an fur [a[a]a].

b) Geben Sie in einer Tabelle alle Worte der Langen 1 bis 6 der zugehorigen SpracheL = L(G) an.

c) Beschreiben Sie die Sprache L in ein bis zwei Satzen.

d) Geben Sie einen Kellerautomaten an, der L akzeptiert.

e) Welchen Chomsky Typ hat diese Sprache? (Begrundung!)

Aufgabe 24 Konstruieren Sie eine Turingmaschine M zur Berechnung der Paritat desEingabewortes w ∈ {0, 1}∗. Die Paritat p eines Wortes w ist Null wenn w eine geradeZahl von Einsen enthalt und Eins sonst. M startet in der Konfiguration . . . 2z0w2 . . . mitStartzustand z0 und stoppt im Endzustand ze in der Konfiguration . . . 2w2zep2 . . ..

Aufgabe 25 Entwerfen Sie fur folgende Aufgaben je eine Turingmaschine:

a) Loschen des gesamten Bandes, d.h. alle Einsen und Nullen werden durch 2 ersetzt.

b) Invertieren der Eingabe, d.h. jede Null wird zur Eins und umgekehrt.

c) Multiplikation der Eingabe mit 2.

d) Kopieren der Eingabe, d.h. die Maschine erzeugt aus der Startkonfiguration

. . . 222z0x1x2 . . . xn222 . . .

die Stopkonfiguration

. . . 222z0x1x2 . . . xn2x1x2 . . . xn222 . . .

1.11 Ubungen 33

Aufgabe 26 Suchen Sie im Internet nach Simulatoren fur Turingmaschinen sowie nachOnline Beschreibungen, etc.

Aufgabe 27 Entwerfen Sie moglichst fleißige Biber mit 2, 3, und 4 Zustanden.

Aufgabe 28 Ziel dieser Aufgabe ist es, ein Programm zu schreiben, das die Funktion Σ(n)berechnet.

a) Beschreiben Sie solch ein Programm.

b) Welches Problem tritt hier auf?

c) Warum ist es viel einfacher, ein Programm zu schreiben, das eine untere Schrankefur Σ(n) berechnet?

Kapitel 2

Berechenbarkeit und Komplexitat

2.1 Berechenbarkeit

Aus der Komplexitat von Algorithmen und auch aus dem Gebiet der formalen Sprachenwissen wir, das es, abhangig vom jeweiligen Maschinenmodell unterschiedlich schwierigeBerechnungsaufgaben gibt. Zum Beispiel kann ein endlicher Automat das Wortproblemfur regulare Sprachen losen. Das Wortproblem fur kontextfreie Sprachen dagegen konnenendliche Automaten nicht (allgemein) losen.

Wir wollen nun die Berechnungsprobleme einteilen in verschiedene Klassen entsprechendihrer Schwierigkeit, angefangen von den einfachen bis hin zu den unlosbaren Problemen. AlsMaschinenmodell werden wir deterministische und nichtdeterministische Turingmaschinenbetrachten.

Die Turingmaschine wird aus folgenden drei Grunden fur unsere Betrachtungen gewahlt:

• Die Turingmaschine kann genau die intuitiv berechenbaren Probleme losen (Church-sche These, unbewiesen).

• Die Turingmaschine ist gleich machtig wie der von-Neumann-Rechner, das heißt, dassjedes Problem, das ein von-Neumann-Rechner lost auch von einer Turingmaschinegelost werden kann und umgekehrt.

• Die Turingmaschine ist wesentlich einfacher aufgebaut als ein von-Neumann-Rechnerund daher fur theoretische Analysen einfacher zu handhaben.

Zuerst wenden wir uns der Berechenbarkeit zu. Wir werden versuchen, zu verstehen, welcheProbleme fur Turingmaschinen (und damit fur Computer) losbar und welche unlosbar sind.

Definition 2.1 Ein Berechnungsproblem (genauer: eine Funktion f : Nn 7→ N) heißt(Turing)-berechenbar, wenn es eine Turingmaschine gibt, die fur eine beliebige In-stanz des Problems nach endlicher Zeit halt und eine korrekte Losung berechnet.

Wegen dem oben gesagten sind alle berechenbaren Probleme durch ein Programm einer(Turing-machtigen) Programmiersprache losbar.

Wir erinnern daran, daß Turingmaschinen genau die Typ-0-Sprachen erkennen, das heißtdie Turingmaschine lost das Wortproblem fur Typ-0-Sprachen.

2.1 Berechenbarkeit 35

Ein Spezialfall der Berechenbarkeit fur binare Entscheidungsprobleme, wie zum Beispieldie Frage ob eine boole’sche Formel erfullbar ist oder nicht, ist die Entscheidbarkeit.

Definition 2.2 Ein Entscheidungsproblem (genauer: eine Funktion f : Nn 7→ {0, 1})heißt entscheidbar, wenn es eine Turingmaschine gibt, die fur eine beliebige Instanzdes Problems nach endlicher Zeit halt und eine korrekte Losung berechnet.

Zu jedem Entscheidungsprobleme gibt es eine aquivalente Formulierung als Wortproblemder Sprache aller Eingaben w mit f(w) = 1. In anderen Worten:

Das Entscheidungsproblem zu einer Funktion f : Nn 7→ {0, 1} ist die SpracheL = {w ∈ Nn|f(w) = 1}.

Beispiel 2.1

Entscheidungsproblem Sprache

Ist eine Liste sortiert? sortierte ListenErfullbarkeit aussagenlogischer Formeln erfullbare aussagenlogische Formeln

Ist eine Zahl prim? Primzahlen

Die Losung eines Entscheidungsproblems ist also aquivalent zur Losung des Wortproblemsder zugehorigen Sprache.

Im Folgenden werden wir aufgrund dieser Aquivalenz bei Entscheidungsproblemen nichtmehr zwischen Problem und Sprache unterscheiden.

Zunachst wollen wir einige Probleme angeben, die von Turingmaschinen nicht gelost werdenkonnen.

Besonders interessant ist die Tatsache, daß es formal wohl definierte praktisch relevanteProbleme gibt, die Turingmaschinen (prinzipiell) nicht losen konnen. Wir werden namlichzeigen dass es viel mehr Funktionen gibt als es Turingmaschinen, bzw. Programme gebenkann. Daraus folgt dann, dass die uberwiegende Anzahl von Funktionen nicht berechenbarist.

2.1.1 Das Halteproblem fur Turingmaschinen

Formal ist eine Turingmaschine ein 7-Tupel aus endlichen Mengen. Das heißt jede Tu-ringmaschine laßt sich (wie jedes Programm auch) durch eine endliche Zeichenkette (zumBeispiel bestehend aus ASCII-Zeichen) beschreiben. Diese endliche Zeichenkette kann mannun binar kodieren. Interpretiert man diesen Binarcode als naturliche Zahl, so erhalt mandie eindeutige Nummer dieser Maschine.

Zu jeder Turingmaschine gibt es also deren eindeutige Nummer. Sicher gibt es eine Turing-maschine mit der kleinsten Nummer wmin. Also stellen die Zahlen 1 bis wmin − 1 (noch)keine Turingmaschinen dar. Damit wir umgekehrt auch fur jede naturliche Zahl eine Tu-ringmaschine erhalten, definieren wir

Mw =

{die zu w gehorende Turingmaschine falls w eine Turingmaschine beschreibt

Mw+1 falls w keine Turingmaschine beschreibt

36 2 Berechenbarkeit und Komplexitat

Diese Funktion ordnet jeder naturlichen Zahl eine Turingmaschine zu.

Es gibt also abzahlbar viele Turingmaschinen! Da die Zahl der Funktionen von naturlichenZahlen auf naturliche Zahlen aber uberabzahlbar ist (siehe unten), gibt es also mehr Funk-tionen als Turingmaschinen. Zwangslaufig sind also viele Funktionen (die weitaus uberwie-gende Anzahl) nicht berechenbar. Dies wollen wir festhalten.

Satz 2.1 Es gibt abzahlbar viele Turingmaschinen. Die Zahl der Funktionen von natur-lichen Zahlen auf naturliche Zahlen ist uberabzahlbar. Also sind viele Funktionen (dieweitaus uberwiegende Anzahl) nicht berechenbar.

Beweis: Zu zeigen ist nur noch, dass die Menge aller Funktionen f : N 7→ N nichtabzahlbar ist. Das zeigen wir durch Widerspruchsbeweis. Der Beweis lauft analog zumBeweis der Uberabzahlbarkeit der reellen Zahlen (Ubung).

Wir nehmen an die Zahl der Funktionen von den naturlichen Zahlen auf die naturli-chen Zahlen sei abzahlbar. Die Funktionen lassen sich also durchnummerieren z.B. alsf1, f2, f3, . . .. Eine Wertetabelle fur alle Funktionen hat folgendes Aussehen:

x 1 2 3 4 5 . . .

f1(x) f1(1) f1(2) f1(3) f1(4) f1(5) . . .f2(x) f2(1) f2(2) f2(3) f2(4) f2(5) . . .f3(x) f3(1) f3(2) f3(3) f3(4) f3(5) . . .f4(x) f4(1) f4(2) f4(3) f4(4) f4(5) . . .f5(x) f5(1) f5(2) f5(3) f5(4) f5(5) . . .. . . . . . . . . . . . . . . . . . . . .

Wir konstruieren nun eine Funktion g : N 7→ N, die in dieser Wertetabelle noch nichtenthalten ist. g ist wie folgt definiert:

x 1 2 3 4 5 . . .

g(x) f1(1) + 1 f2(2) + 1 f3(3) + 1 f4(4) + 1 f5(5) + 1 . . .

g hat die Eigenschaft, sich von jeder der Funktionen an mindestens einer Stelle x ∈ N zuunterscheiden. Dies ist jedoch ein Widerspruch zur Annahme, dass es nur abzahlbar vieleFunktionen von N nach N gibt. Also ist die Behauptung bewiesen. 2

Wir wollen nun von einer speziellen Funktion zeigen, daß sie nicht entscheidbar ist. Dassogenannte Halteproblem fur Turingmaschinen besteht darin, eine ganz besondere Turing-maschine zu finden, die fur eine beliebige Turingmaschine Mw und deren Eingabe x ent-scheiden soll, ob diese Maschine halt. w sei die binare Kodierung von Mw.

Definition 2.3 Das (allgemeine) Halteproblem ist die Sprache

H = {w#x |Mw angesetzt auf x halt}.


Satz 2.2 Das Halteproblem H ist nicht entscheidbar.

Beweis: (einfache Variante) Angenommen, das Programm halt(w,x) lost das Haltepro-blem H(w, x), das heisst, bei Eingabe eines Programmes w und dessen Eingabe x gibt esden Wert 1 aus, wenn w angesetzt auf x halten wurde und 0 andernfalls. Nun bauen wirfolgendes neue Programm unmoglich:

unmoglich(int i){

if( halt(unmoglich,0))while( TRUE ) printf(”das kann noch dauern ...”);

elseprintf(”0”);

}

Dieses Programm kann es aber nicht geben, denn wenn (nach Voraussetzung) halt zumSchluß kommt, dass es terminiert, dann halt es gerade nicht und umgekehrt. Schuld an die-sem Widerspruch kann aber nur die Voraussetzung sein, dass halt das Halteproblem lost. 2

Beweis: (elegante, allgemeine Variante) Angenommen, H sei entscheidbar. Dann gibt eseine Turingmaschine H(w, x), welche entscheidet, ob die Turingmaschine Mw bei Eingabevon x halt. Wir betrachten die Tafel der berechneten Werte aller Turingmaschinen aufallen Eingaben. In die Tafel wird uberall dort, wo eine Maschine nicht anhalt, oder nichtin einem Endzustand halt, das Symbol ∞ eingetragen.1

Es sei

H(w, x) =

{1 falls Mw(x)halt0 sonst

Mw(X) Eingabe x →1 2 3 4 5 . . .

1 ∞ ∞ ∞ ∞ ∞ . . .Turing 2 ∞ 1 0 2 7 . . .masch. 3 1 ∞ 1 ∞ 1 . . .

Nr. 4 2 2 0 3 1 . . .w 5 1 0 1 1 0 . . .

↓ ......

......

......

Nun wenden wir auf diese Tabelle die Turingmaschine H(w, x) an und bestimmen die(Turing berechenbare) Funktion

Q(w, x) =

{0 falls H(w, x) = 0

Mw(x) falls H(w, x) = 1

1 Die konkret eingetragenen Werte sind zufallig gewahlt. Eine systematische Aufzahlung der ersten n Zeilenware moglich, wird jedoch der Einfachheit weggelassen.


Falls Mw(x) halt, verhalt sich Q(w, x) gleich wie Mw(x). Andernfalls ist Q(w, x) = 0 .

Q(w, x) x →1 2 3 4 5 . . .

1 0 0 0 0 0 . . .2 0 1 0 2 7 . . .3 1 0 1 0 1 . . .4 2 2 0 3 1 . . .

w 5 1 0 1 1 0 . . .

↓ ......

......

......

Nun nehmen wir alle Diagonalelemente von Q, d.h. Q(w,w) und addieren zu jedem 1. Dieresultierende Folge (1 + Q(w, w))w∈N ist offensichtlich Turing-berechenbar. Sie kommtjedoch nicht in der Tabelle als Zeile vor, im Widerspruch zur Tatsache, daß in der Tabellejede Turingmaschine (und damit jede Turing-berechenbare Funktion) vorkommt. 2

Bemerkung: Die Zahl der Funktionen von N nach N ist uberabzahlbar. Die Zahl derTuringmaschinen ist jedoch nur abzahlbar. Daher kann nicht jede Funktion von N nach N(Turing) berechnet werden. Das Halteproblem ist eine dieser nicht berechenbaren Funktio-nen.

Satz 2.3 Die Funktion S(n), die angibt, wie gross die maximale Zahl von Schritten ist, dieeine Turingmaschine mit n Zustanden (ohne Endzustand) und einem Bandalphabet mitzwei Zeichen machen kann, bevor sie anhalt, ist nicht berechenbar.

Beweis: Angenommen, S(n) ware berechenbar. Dann ware das Halteproblem entscheid-bar. Um das Halteproblem fur eine gegebene Turingmaschine M mit n Zustanden undEingabe x zu losen, musste man nur S(n) berechnen und dann M auf der Eingabe xstarten. Nach hochstens S(n) Schritten steht die Antwort fest. S(n) kann also nicht bere-chenbar sein. 2

Satz 2.4 Die Funktion Σ(n), die angibt, wie gross die maximale Zahl von Einsen ist, die einfleißiger Biber mit n Zustanden (ohne Endzustand) ausgeben kann, ist nicht berechenbar.

Beweis: Angenommen, Σ(n) ware berechenbar und EvalΣ sei solch eine Turingmaschine,welche gestartet auf einem Band mit n Einsen Σ(n) berechnet und am Ende Σ(n) Einsenauf das Band schreibt. EvalΣ habe N Zustande. N ist konstant und n variabel.

Nun konstruieren wir eine neue Turingmaschine. Es sei Verdopple eine TM, die die Zahlder Einsen auf dem Band verdoppelt. Diese Maschine benotigt wenige Zustande. Außer-dem sei SchreibeEinsen eine TM, mit N Zustanden, die N Einsen auf das Band schreibt.Nun betrachten wir die Komposition SchreibeEinsen | Verdopple | Verdopple | EvalΣ. DieseMaschine kommt mit etwas mehr als 2N Zustanden aus, schreibt aber Σ(4N) Einsen aufdas Band. Dies steht im Widerspruch zur Definition von Σ(n). 2


2.1.2 Die Ackermannfunktion

Definition 2.4 Eine Funktion, die nicht ganz so schnell wachst wie S(n) und Σ(n) istdie wie folgt definierte Ackermannfunktion:

a(0, n) = n + 1

a(m, 0) = a(m− 1, 1) fur m > 0

a(m, n) = a(m− 1, a(m, n− 1)) fur m > 0, n > 0

Wertetabelle:

m\n 0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 7 8 9 10 11 122 3 5 7 9 11 13 15 17 19 21 233 5 13 29 61 125 253 509 1021 2045 4093 8189

n 0 1 2 3 4 . . . n

a(4, n) 13 65533 265536 − 3 a(3, 265536 − 3) a(3, a(4, 3)) . . . 22...2︸︷︷︸(n+3) mal

−3

Schon die Berechnung von a(2, 1) ist nicht ganz einfach:

a(2, 1) = a(1, a(2, 0))

= a(1, a(1, 1))

= a(1, a(0, a(1, 0)))

= a(1, a(0, a(0, 1)))

= a(1, a(0, 2))

= a(1, 3)

= a(0, a(1, 2))

= a(0, a(0, a(1, 1)))

= a(0, a(0, a(0, a(1, 0))))

= a(0, a(0, a(0, a(0, 1))))

= a(0, a(0, a(0, 2)))

= a(0, a(0, 3))

= a(0, 4)

= 5

Die Ackermannfunktion ist berechenbar (siehe Aufgabe ??).


Definition 2.5 Eine Sprache L heißt halbentscheidbar, wenn es eine deterministischeTuringmaschine gibt, die fur jedes Wort w ∈ L nach endlicher Zeit terminiert und mit“ja” antwortet. Fur Worte w /∈ L gibt die Maschine “nein” aus oder halt nicht.

Definition 2.6 Eine Sprache L heißt rekursiv aufzahlbar, wenn gilt L ={w1, w2, w3, . . .} und wenn es eine deterministische Turingmaschine gibt, welche die Ele-mente der Folge {w1, w2, w3, . . .} nacheinander berechnen (aufzahlen) kann.

Satz 2.5 Eine Sprache ist rekursiv aufzahlbar genau dann wenn sie halbentscheidbar ist.

Beweis: “⇒”: Sei L rekursiv aufzahlbar. Da jedes Wort aus L nach endlicher Zeit erzeugtwird, ist sie halbentscheidbar. Das Entscheidungsverfahren fur ein vorgegebenes Wort wmuß nur zusatzlich bei jedem erzeugten Wort prufen, ob es gleich w ist.

Die andere Richtung ist etwas schwieriger (siehe [9]). 2

Satz 2.6 Das Halteproblem fur Turingmaschinen ist halbentscheidbar.

Beweis: Es ist nicht schwierig, einen Turingmaschinensimulator zu programmieren. Die-sen verwenden wir um die zu uberprufende Turingmaschine Mw mit der Eingabe x zusimulieren. Wenn die simulierte Maschine halt, wird “ja” ausgegeben. 2

2.1.3 Das Post’sche Korrespondenzproblem

Beim Post’schen Korrespondenzproblem ist eine endliche Folge von Wortpaaren (x1, y1),(x2, y2), . . . (xk, yk) mit xi, yi ∈ {0, 1}+ gegeben. Gesucht ist eine Folge von Indizes i1, i2, . . . , inmit xi1 , xi2 , . . . xin = yi1 , yi2 , . . . yin .

Beispiel 2.2 Das Problem ((000, 000), (11, 110), (01, 100), (010, 10), (0001, 010)) besitzt dieLosung (2, 3, 5, 1, 4), denn

x2, x3, x5, x1, x4 = 11010001000010 = y2, y3, y5, y1, y4.

Satz 2.7 Das Post’sche Korrespondenzproblem ist halbentscheidbar.

Das Post’sche Korrespondenzproblem ist rekursiv aufzahlbar, denn es gibt ein Programm,das kombinatorisch alle Folgen von Indizes i1, i2, . . . , in aufzahlen und deren Zugehorigkeitzur Sprache des Post’sche Korrespondenzproblems testen kann (siehe Aufgabe 33).

2.2 Komplexitatsklassen 41

Satz 2.8 Das Post’sche Korrespondenzproblem ist nicht entscheidbar.

Ein Beweis kann z.B. in [9] nachgelesen werden. Die Aussage des Satzes ist anschaulichsehr plausibel (siehe Ubung 33).

2.2 Komplexitatsklassen

Eine nichtdeterministische Turingmaschine unterscheidet sich von einer deterministischendarin, dass bei der nichtdeterministischen Turingmaschine fur ein gelesenes Bandzeichen ineinem bestimmten Zustand mehrere verschiedene Aktionen moglich sind. Ein Problem giltals gelost von einer derartigen Maschine, wenn es eine Folge von Aktionen gibt, die zurLosung des Problems fuhrt. Nach unserem heutigen Wissen ist dies eine nicht besonderspraktische Maschine. Wer sagt ihr wie sie an den kritischen Stellen verzweigen soll? EinOrakel!?

Es ware aber auch denkbar, dass an jeder Verzweigung die Maschine Kopien von sicherzeugt und zwar so viele wie es Zweige gibt. Das funktioniert in der Praxis aber nur mitunbeschrankten Ressourcen an Parallelitat.

Definition 2.7 Die Klasse P umfaßt alle Berechnungsprobleme, die von einer determi-nistischen Turingmaschine in polynomieller Zeit gelost werden konnen. Die Klasse NPumfaßt alle Berechnungsprobleme, die von einer nichtdeterministischen Turingmaschinein polynomieller Zeit gelost werden konnen.

Es folgt sofort, dassP ⊆ NP,

denn nichtdeterministische Turingmaschinen sind machtiger. Nun wollen wir einige Proble-me in NP betrachten.

Satz 2.9 Das aussagenlogische Erfullbarkeitsproblem SAT fur Formeln in konjunktiverNormalform ist in NP .

Beispiel 2.3 (A ∨B ∨ ¬C) ∧ (C ∨D) ∧ (¬A ∨ ¬C) ist in konjunktiver Normalform.

Eine nichtdeterministische Turingmaschine rat fur jede Aussagevariable einer Formel einenWahrheitswert, setzt diesen ein und uberpruft die Gultigkeit in linearer Zeit.2

Eine deterministische Turingmaschine hatte hier (insbesondere beim Raten) ihre Probleme.Dies glauben jedenfalls die Fachleute, denn es ist bis heute kein Programm bekannt, welchesSAT in polynomieller Zeit lost.

Neben vielen anderen sind folgende Probleme in NP .

2 Falls die Formel unerfullbar ist, kann aufgrund der bekannten linearen Komplexitat des Uberprufens nacheiner vorher festgelegten Zeit abgebrochen werden und “unerfullbar” ausgegeben werden.


TSP: Die Entscheidungsvariante des Travelling-Salesman-Problems: Ist die kurzeste Rund-reise durch n gegebene Stadte mit Entfernungsmatrix M kurzer als k?

HC: Enthalt ein ungerichteter Graph einen Hamiltonschen Kreis? Dies ist ein geschlosse-ner Weg, der jeden Knoten genau einmal enthalt.

CLIQUE: Die Entscheidungsvariante des Cliquenproblems. Enthalt ein Graph mit n Kno-ten eine Clique mit k ≤ n Knoten? Eine Clique ist ein vollstandig vernetzter Graph.

COMP: Gibt es fur eine ganze Zahl k ganze Zahlen m, n > 1 mit k = mn? (Ist kPrimzahl?)

GISO: Sind zwei Graphen G = (V, E) und G′ = (V ′, E ′) isomorph, d.h. gibt es einebijektive Funktion f : V → V ′ so dass (u, v) ∈ E genau dann wenn (f(u), f(v)) ∈ E ′.

Da P ⊆ NP ist naturlich jedes der einfachen Entscheidungsprobleme aus P (zum Beispieldas Wortproblem fur regulare Sprachen) auch in NP . Die hier genannten Probleme sindallerdings als schwierig bekannt.

2.2.1 Platzkomplexitat

Definition 2.8 PSPACE enthalt genau die Sprachen L, fur die es eine deterministischeTuringmaschine T gibt, die L entscheidet und fur die die Zahl der maximal verwendetenBandstellen hochstens polynomiell mit der Eingabelange n wachst. Analog ist NPSPACEfur nichtdeterministische Turingmaschinen definiert.

Beispiel 2.4 Das Problem SAT ist in PSPACE. Dies beweist man, indem man zeigt,dass das Uberprufen aller Belegungen der Variablen einer SAT-Formel mittels Tiefensuchedurchgefuhrt werden kann (siehe [12], Aufgabe 2.5).

2.3 NP-Vollstandigkeit

2.3.1 Polynomielle Transformation

Um Probleme bezuglich ihrer Schwierigkeit anordnen zu konnen, benotigen wir eine Mog-lichkeit, Probleme bezuglich ihrer Schwierigkeit zu vergleichen. Aussagen der Art

“Problem P2 ist mindestens so schwierig wie Problem P1”

sind gefordert. Informal bezeichnen wir ein Problem P2 als mindestens so schwierig wie P1,wenn sich P1 mit wenig Aufwand auf P2 zuruckfuhren laßt.

2.3 NP-Vollstandigkeit 43

Definition 2.9 Eine polynomielle Transformation einer Sprache L1 ⊂ Σ∗1 auf eine

Sprache L2 ⊂ Σ∗2 ist eine mit polynomieller Komplexitat berechenbare Funktion f :

Σ∗1 → Σ∗

2 mit∀w ∈ Σ∗

1 w ∈ L1 ⇔ f(w) ∈ L2.

Laßt sich L1 auf L2 polynomiell transformieren, so schreiben wir L1 � L2.

Beispiel 2.5 Das Problem HC laßt sich polynomiell transformieren auf das Problem TSP.Wie?

Definition 2.10 Eine Sprache L ∈ NP heißt NP-vollstandig, wenn fur alle anderenSprachen L′ ∈ NP gilt L′ � L, d.h. wenn sich alle anderen Sprachen polynomiell auf Ltransformieren lassen.

Lemma 2.1 Wenn fur ein NP-vollstandiges Problem gezeigt wird, dass es in P ist, so giltP = NP .

Beweis: Sei L eine NP-vollstandige Sprache fur die gezeigt ist, dass sie sogar in Pist. Das heißt, das Wortproblem fur L ist polynomiell losbar und fur die Rechenzeit giltTL(n) = O(nk) mit einer Konstante k. Da L NP-vollstandig ist, sind alle L′ ∈ NP poly-nomiell transformierbar auf L. Die Transformation f fur ein beliebiges L′ hat also auchpolynomielle Rechenzeit Tf (n) = O(nm). Damit kann das Problem L′ gelost mit einerGesamtkomplexitat von

TL′(n) = TL(n) + Tf (n) = O(nm) + O(nk) = O(nm + nk) = O(nmax{m,k}).

Das Wortproblem fur L′ ist damit polynomiell losbar. Also gilt fur alle Sprachen L′ ∈ NPauch L′ ∈ P und damit P = NP . 2

Die Wissenschaftler glauben heute, dass P 6= NP , denn die NP-vollstandigen Problemesind so schwierig, dass man es fur unmoglich halt auch nur eines (und damit alle!) polyno-miell zu losen. Dies ist aber nicht bewiesen. Daher:

Vermutung: P 6= NP .

Wir wollen nun die bisher bekannten Problemklassen grafisch veranschaulichen. Die fol-gende Abbildung beinhaltet die soeben formulierte Vermutung.


alle Berechnungsprobleme

rekursiv aufzahlbare, bzw. halbentscheidbare Probleme (Typ-0-Sprachen)

berechenbare, bzw. entscheidbare Probleme (Typ-1-Sprachen)

NP-harte Probleme

NP NP-vollstandige Probleme

P

Die oben genannten Probleme ordnen sich folgendermassen in das Bild ein [11]: TSP, HCund CLIQUE sind NP-vollstandig. GISO ist noch unbekannt. d.h. es ist noch nicht bekanntob es NP-vollstandig ist. COMP ist in P. Alle Probleme sind in NP.

Da es durchaus noch schwierigere Probleme gibt als die NP-vollstandigen Probleme, ist essinnvoll, sich zu fragen, ob sich ein Problem aus NP auf irgend ein Problem polynomielltransformieren lassen.

Definition 2.11 Eine Sprache L heißt NP-hart, falls sich alle Sprachen aus NP poly-nomiell auf L transformieren lassen.

2.4 Ubungen

Aufgabe 29

a) Wieviele verschiedene Funktionen gibt es von einer n-elementigen Menge auf sichselbst?

b) Wieviele invertierbare Funktionen gibt es von einer n-elementigen Menge auf sichselbst?

c) Wir betrachten Funktionen f : {0, 1}n 7→ {0, 1}m von Bit-Vektoren auf Bit-Vektoren.Wieviele verschiedene Funktionen gibt es von diesem Typ?

d) Fur welche Werte n, m aus Teilaufgabe c gibt es keine invertierbaren Funktionen?Wieviele invertierbare Funktionen gibt es fur festes n und m?

Aufgabe 30 Vervollstandigen Sie folgende Tabelle:

2.4 Ubungen 45

Entscheidungsproblem Sprache

C-Programme

C-Programme die terminieren

aussagenlogische Formeln

wahre aussagenlogische Formeln

pradikatenlogische Formeln

wahre pradikatenlogische Formeln

gerade Zahlen

Post’sches Korrespondenzproblem

TSP

HC

CLIQUE

GISO

Aufgabe 31 Untersuchen Sie die folgenden Funktionen auf Berechenbarkeit:

a) f : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}∗ → {0, 1} mit f(x) = 1 genau dann, wenn x das Anfangs-stuck der Dezimaldarstellung von π ist. Z.B. ist f(31415) = 1 und f(33333) = 0.

b) g : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}∗ → {0, 1} mit g(x) = 1 genau dann, wenn x irgendwo inder Dezimaldarstellung von π vorkommt.

c) h : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}∗ → {0, 1} mit h(n) = 1 genau dann, wenn irgendwo in derDezimaldarstellung von π eine Folge von mit mindestens n mal der Ziffer 7 vorkommt.

Aufgabe 32 Ist fur jede reelle Zahl r die Funktion fr berechenbar? Es sei fr(x) = 1 genaudann, wenn x das Anfangsstuck der Dezimaldarstellung von r ist.

Aufgabe 33 Post’sches Korrespondenzproblem

a) Losen sie das Problem ((01, 11), (0, 010), (100, 00)).

b) Schreiben Sie ein Programm, das bei Eingabe einer Liste von Paaren uber {0, 1}+dieses Problem lost.

Aufgabe 34 Zeigen Sie: Wenn eine Sprache L halbentscheidbar ist und ihr KomplementL = Σ∗\L auch halbentscheidbar ist, dann ist L entscheidbar.

Aufgabe 35 Geben sie fur die Sprache der geraden Zahlen in Binardarstellung, d.h. uberdem Alphabet {0, 1} eine regulare Grammatik sowie einen regularen Ausdruck an.

Aufgabe 36

a) Zeigen Sie, daß die Programmverifikation – d.h. der Beweis der Korrektheit – furbeliebige C-Programme unentscheidbar ist. Zitieren Sie hierzu einen oder mehrereSatze aus der Vorlesung, bzw. aus dem Buch von U. Schoning.


b) Geben Sie eine unendliche Menge von C-Programmen an, die automatisch verifiziertwerden konnen (mit Begrundung!).

Aufgabe 37 Beschreiben Sie die Menge aller Barbiere, die genau die Personen rasieren,welche sich nicht selbst rasieren. (Tipp: Rasiert sich ein solcher Barbier selbst?)

Literaturverzeichnis

[1] A. Asteroth and C. Baier. Theoretische Informatik. Pearson Studium, 2003. Sehrempfehlenswertes Buch.

[2] J.E. Hopcroft, R. Motwani, and J.D. Ullman. Einfuhrung in die Automatentheorie,Formale Sprachen und Komplexitatstheorie. Pearson Studium, 2002. Der Klassiker,ausfuhrlich, gute Erklarungen.

[3] J.D. Ullman, M.S. Lam, R. Sethi, and A.V. Aho. Compiler. Pearson Studium, 2002.Fur den, der es wirklich wissen will.

[4] G. Vossen and K.U. Witt. Grundkurs Theoretische Informatik. Vieweg, 2006.

[5] N. Blum. Theoretische Informatik. Oldenbourg, 1998. Gutes Buch, Berechenbarkeitund Komplexitat recht kurz, enthalt auch noch Graphen und Algorithmen.

[6] J. Hromkovic. Theoretische Informatik. Teubner, 2007.

[7] I. Wegener. Theoretische Informatik – eine algorithmische Einfuhrung. Teubner Ver-lag, 1993.

[8] I. Wegener. Kompendium Theoretische Informatik – eine Ideensammlung. TeubnerVerlag, 1996. Als Erganzung zur Vorlesung und zum besseren Verstandnis hervorra-gend geeignet. Ohne Formeln wird ein Uberblick vermittelt.

[9] U. Schoning. Theoretische Informatik kurzgefasst. Spektrum Akademischer Verlag,1992. Gutes Buch, aber etwas zu theoretisch fur die FH.

[10] R. Socher. Theoretische Grundlagen der Informatik. Fachbuchverlag Leipzig, 2003.Gutes Buch auf FH-Niveau uber formale Sprachen.

[11] M. Garey and D. Johnson. Computers and Intractability. A Guide to the Theory ofNP-Completeness. Freeman, 1979. Umfassendes Werk zur NP-Theorie mit Tabellevon NP-Problemen.

[12] W. Ertel. Grundkurs Kunstliche Intelligenz. Vieweg-Verlag, 2007.

[13] M. Brill. Mathematik fur Informatiker. Hanser Verlag, 2001. Sehr gutes Buch, dasauch diskrete Mathematik beinhaltet.

[14] P. Tittmann. Graphentheorie. Fachbuchverlag Leipzig, 2003. Sehr gutes Buch mitvielen Beispielen. Leider fehlen die Wegesuchalgorithmen.

[15] T.H. Cormen, Ch.E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MITPress, Cambridge, Mass, 1994. Sehr gute Einfuhrung in die Analyse von Algorithmen.

[16] R. Sedgewick. Algorithmen. Addison-Wesley, Bonn, 1995. Ubersetzung d. engl. Ori-ginals, empfehlenswert.

48 Literaturverzeichnis

[17] A. K. Dewdney. New Turing Omnibus. W.H. Freeman & Company, 1993.

[18] H. Marxen. Busy beaver. http://www.drb.insel.de/~heiner/BB/index.html,2001.

http://www.drb.insel.de/~heiner/BB/index.html

Documents

Theoretische Informatik - hs-weingarten.deertel/vorlesungen/thinf/skript.pdf · 4 1 Formale Sprachen und Maschinenmodelle Fangen wir bei den elementaren Bausteinen an. Deﬁnition