Grundbegriffe der Informatik Tutorium 2 - Tutorium Nr. 16gbi.phil-opp.com/folien-ws2014/2.pdf · 2015. 11. 15. · Outline/Gliederung 1 Nachtrag 2 Wörter 3 Vollständige Induktion

KARLSRUHER INSTITUT FÜR TECHNOLOGIE

Grundbegriffe der InformatikTutorium 2Tutorium Nr. 16

Philipp Oppermann | 9. November 2014

KIT – Universität des Landes Baden-Württemberg und

nationales Forschungszentrum in der Helmholtz-Gemeinschaft

www.kit.edu

http://www.kit.edu

Outline/Gliederung

1 Nachtrag

2 Wörter

3 Vollständige Induktion

4 Binäre Operationen

5 Formale Sprachen

6 Aufgaben

Nachtrag Wörter Vollständige Induktion Binäre Operationen Formale Sprachen Aufgaben

Philipp Oppermann – GBI Tutorium Nr. 16 9. November 2014 2/22

Raumänderung 12.11.

Tutorium nächste Woche (12.11.) verlegt nach SR 148!



Nachtrag

Gn heißt dieses Semester Zn

Zn = {i ∈ N0 | 0 ≤ i ∧ i < n}Menge der ganzen Zahlen von 0 bis n − 1

Z5 = {0, 1, 2, 3, 4}Z0 = {}

Mengendifferenz

M1 \M2 = {x | x ∈ M1 ∧ x /∈ M2}



Alphabete

DefinitionEin Alphabet ist eine endliche, nichtleere Menge von Zeichen.

BeispieleA = {a, b, c, d , e, f , g, h, i, j, k , l,m, n, o, p, q, r , s, t, u, v ,w , x , y , z}Z5 = {0, 1, 2, 3, 4}Y = {♦,♥,♠,♣}

Keine AlphabeteN0, ∅



Wörter

DefinitionEin Wort ist eine surjektive Abbildung w : Zn → A.

BeispielDas wort w = hallo ist die Abbildung w : Z5 → {a, h, l, o} mitw(0) = h,w(1) = a,w(2) = l,w(3) = l,w(4) = o

Länge von w: |w | = 5



Das leere Wort

Definitionε : {} → {} (von Z0 in das leere Alphabet)

ε hat Länge 0 (ist aber trotzdem etwas)

M = {ε} ist keine leere Menge und | {ε} | = 1

ε ist eindeutig



Konkatenation von Wörtern

Feuerwehr · Auto = FeuerwehrAuto

h · a · l · l · o = hallo

ε · ε · w · ε = w

Potenz

Zahlen xk = x · x · x · · · x = xxx · · · x (k-mal)

Wörter wk = w · w · w · · ·w = www · · ·w (k-mal)



Potenzen von Wörtern

Wörter mit Länge nDie Menge aller Wörter der Länge n über dem Alphabet A ist An.

BeispielA = {a, b}

A2 = {aa, ab, ba, bb}A1 = {a, b} = A

A0 = {ε} 6= ∅



Potenzen von Wörtern

Wörter mit Länge nDie Menge aller Wörter der Länge n über dem Alphabet A ist An.

Menge aller Wörter

Die Menge aller Wörter über einem Alphabet A ist A∗ =∞⋃

i=0Ai .

A∗ = A0 ∪ A1 ∪ A2 ∪ · · ·

Achtung

Wenn A = {}, dann ist A0 = {ε}{}∗ = {ε}



Induktive Definition der Potenz

Definition

w0 = ε

∀k ∈ N0 : wk+1 = wk · w

Beispiel

w2 = w1+1 = w1 · w = w0+1 · w = ε · w · w = w · w



Vollständige Induktion

PrinzipWenn man für eine Aussage A(n) (n ∈ N0) weiß:

es gilt A(0)

und es gilt ∀n ∈ N0 : (A(n)⇒ A(n + 1))

dann gilt auch: ∀n ∈ N0 : A(n)

Beweise1 Induktionsanfang (IA): Zeigen, dass A(0) gilt.2 Induktionsvoraussetzung (IV): „Für beliebiges aber festes n ∈ N0

gilt A(n).“3 Induktionsschritt (IS): Zeigen dass auch A(n + 1) gilt, wenn A(n)

gilt.



Aufgabe

Zeige durch vollständige Induktion: ∀n ∈ N+ : n3 + 5n ist durch 6 teilbar.



Binäre Operationen

DefinitionEine binäre Operation auf einer Menge M ist eine Abbildung� : M ×M → M.

statt +(3, 8) = 11 schreibt man 3 + 8 = 11

� ist kommutativ⇐⇒ ∀x , y ∈ M : x � y = y � x

� ist assoziativ⇐⇒ ∀x , y , z ∈ M : (x � y) � z = x � (y � z)

Beipiel

Die Operation � :

{N0 → N0

(x , y) 7→ x + yist kommutativ und assoziativ.

Die Konkatenation von Wörtern ist assoziativ, aber nicht kommutativ.



Formale Sprachen

DefinitionEine formale Sprache über einem Alphabet A ist eine Teilmenge L ⊆ A∗.

BeispielL = {class, if , int, . . . } = Sprache der Java Schlüsselwörter

L = {a, b}∗ \ {w1abw2 | w1,w2 ∈ {a, b}∗} = Sprache der Wörterohne Teilwort ab = {w1w2 | w1 ∈ {b}∗ ∧ w2 ∈ {a}∗}

Achtungabc ist ein Wort

{abc} ist eine Sprache



Produkt von Sprachen

DefinitionL1 · L2 = {w1w2 | w1 ∈ L1 ∧ w2 ∈ L2} heißt das Produkt der formalenSprachen L1 und L2.

BeispielA = {a, b} , L1 = {aa, b} , L2 = {bb, bbb}⇒ L1 · L2 = {aabb, aabbb, bbb, bbbb}L · {ε} = L = {ε} · LL1 = {bn | n ∈ N0} , L2 = {an | n ∈ N0}⇒ L1L2 = {bnam | n,m ∈ N0} = {b}∗ {a}∗



Potenzen von Sprachen

Definition (induktiv)

L0 = {ε}∀k ∈ N0 : Lk+1 = L · Lk

BeispielL = {anbn | n ∈ N+}

L0 = {ε}L1 = L = {ab, aabb, aaabbb, aaaabbbb, . . . }L2 = L · L = {an1bn1an2bn2 | n1, n2 ∈ N+} ={ab · ab, ab · aabb, ab · aaabbb, . . . } ∪{aabb · ab, aabb · aabb, aabb · aaabbb, . . . } ∪{aaabbb · ab, aaabbb · aabb, aaabbb · aaabbb, . . . } ∪ · · ·



Konkatenationsabschluss

Definition

L∗ =∞⋃

i=0Li und L+ =

∞⋃i=1

Li („ε-frei“)

Achtung

ε ∈ L∗ =⇒ {}∗ = {ε}Es kann auch ε ∈ L+ sein, nämlich wenn ε ∈ L.

Beispiel

L = {a}∗ {b}∗

L∗ = {a, b}∗

L+ = {a, b}∗



Aufgabe 1

Beweise: L∗ · L = L+

Lösung⊆:Wenn w ∈ L∗ · L, dann ist w = w ′x mit w ′ ∈ L∗ und x ∈ L.Also existiert ein i ∈ N0 mit w ′ ∈ Li .Also w = w ′x ∈ Li · L = Li+1.Da i + 1 ∈ N+, ist Li+1 ⊆ L+, also w ∈ L+.

⊇: Wenn w ∈ L+, dann existiert ein i ∈ N+ mit w ∈ Li .Da i ∈ N+ ist i = j + 1 für ein j ∈ N0,also ist für ein j ∈ N0: w ∈ Lj+1 = Lj · L.also w = w ′x mit w ′ ∈ Lj und x ∈ L .Wegen Lj ⊆ L∗ ist w = w ′x ∈ L∗ · L.



Aufgabe 2

Es sei A = {a, b} und L = {aa, aaa, b}.Geben Sie (wenn möglich) für folgende Sprachen je 2 Wörter über A an,die in der Sprache liegen, und je 2 Wörter über A, die nicht in der Spracheliegen.

1 L1 ={

w | w ∈ L2 ∧ w ∈ L3}

2 L2 = {w ∈ A∗ | ∃u ∈ A∗ : ∃v ∈ L : w = uv}3 L3 =

{w ∈ L∗ | ∃u ∈ A∗ : uw = w2u

}Lösung

1 aaaaaa ist einziges Wort ∈ L und z.B. a, b /∈ L2 z.B. aa, ab ∈ L und z.B. ε, a, ba /∈ L3 ε ist einziges Wort ∈ L und z.B. a, b /∈ L



Aufgabe 3

L1 = {ε} ∪ {a} · L1 ∪ {b} · L1 ∪ L1 · {c}L2 = {ε} ∪ {a} · L2 · {a} ∪ {b} · L2 · {b} ∪ L2 · L2

1 Zu welcher/n Sprachen gehören die folgenden Wörter?w1 = abbabb,w2 = abaccb,w3 = aabaa,w4 = baabaabb

2 Welche Wörter der Länge 4 gehören zu L2?3 Schreibe L1 als nicht rekursive Konkatenation von Sprachen.



Aufgabe 3

Lösung1 w1 ∈ L1 ∧ w1 ∈ L2

w2 /∈ L1 ∧ w2 /∈ L2

w3 ∈ L1 ∧ w3 /∈ L2

w4 ∈ L1 ∧ w4 ∈ L2

2 aaaa, bbbb, aabb, bbaa, abba, baab3 {a, b}∗ · {c} ∗



Documents

Grundbegriffe der Informatik Tutorium 2 - Tutorium Nr. 16gbi.phil-opp.com/folien-ws2014/2.pdf · 2015. 11. 15. · Outline/Gliederung 1 Nachtrag 2 Wörter 3 Vollständige Induktion