Folien - Grundbegriffe der Informatik

Grundbegriffe der Informatik
Übung
Simon Wacker
Karlsruher Institut für Technologie
Wintersemester 2015/2016
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
1/9
Regex-Bäume — Anzahl
A = {a, b}
Frage: Anzahl Regex-Bäume über A der Höhe 0?
Antwort:
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
2/9
Regex-Bäume — Anzahl
A = {a, b}
Frage: Anzahl Regex-Bäume über A der Höhe 0?
Antwort: 3
a
GBI — Grundbegriffe der Informatik
b
/
O
Karlsruher Institut für Technologie
2/9
Regex-Bäume — Anzahl
A = {a, b}
Frage: Anzahl Regex-Bäume über A der Höhe 1?
Antwort:
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
2/9
Regex-Bäume — Anzahl
A = {a, b}
Frage: Anzahl Regex-Bäume über A der Höhe 1?
Antwort: 3 + 3 · 3 + 3 · 3 = 21
*
.
|
?
?
?
?
?
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
2/9
Regex-Bäume — Anzahl
A = {a, b}
Frage: Anzahl Regex-Bäume über A der Höhe 2?
Antwort:
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
2/9
Regex-Bäume — Anzahl
A = {a, b}
Frage: Anzahl Regex-Bäume über A der Höhe 2?
Antwort:
21 + (21 · 21 + 3 · 21 + 21 · 3) + (21 · 21 + 3 · 21 + 21 · 3) = 1155
|
.
*
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
2/9
Regex-Bäume — Kleinste Anzahl Knoten
A = {a, b}
Frage: Kleinste Anzahl Knoten von Regex-Bäumen der Höhe
n?
Antwort:
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
3/9
Regex-Bäume — Kleinste Anzahl Knoten
A = {a, b}
Frage: Kleinste Anzahl Knoten von Regex-Bäumen der Höhe
n?
Antwort: n + 1
*
*
..
.
*
a
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
3/9
Regex-Bäume — Größte Anzahl Knoten
A = {a, b}
Frage: Größte Anzahl Knoten von Regex-Bäumen der Höhe
n?
Antwort:
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
4/9
Regex-Bäume — Größte Anzahl Knoten
A = {a, b}
Frage: Größte Anzahl Knoten von Regex-Bäumen der Höhe
n?
Antwort:
n
X
|
2i = Num2 (1n+1 )
i=0
.
= Num2 (10n+1 ) − 1
= 2n+1 − 1
GBI — Grundbegriffe der Informatik
...
.
...
...
Karlsruher Institut für Technologie
...
4/9
Distributivgesetz
A Alphabet
R 1 , R 2 , R 3 reguläre Ausdrücke über A
Behauptung: h(R 1 |R 2 )R 3 i = hR 1R 3 |R 2R 3 i
Beweis: Es gilt
h(R 1 |R 2 )R 3 i = h(R 1 |R 2 )i · hR 3 i
= (hR 1 i ∪ hR 2 i) · hR 3 i
= (hR 1 i · hR 3 i) ∪ (hR 2 i · hR 3 i)
= hR 1R 3 i ∪ hR 2R 3 i
= hR 1R 3 |R 2R 3 i.
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
5/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
6/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
0
(...)*
GBI — Grundbegriffe der Informatik
Akzeptierender Anfangszustand
Karlsruher Institut für Technologie
6/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
0
...|...
GBI — Grundbegriffe der Informatik
Zwei Teile
Karlsruher Institut für Technologie
6/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
a
1
a...
GBI — Grundbegriffe der Informatik
0
Mit a in neuen Zustand
Karlsruher Institut für Technologie
6/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
a
0
1
a
b
2
...(ab)*...
GBI — Grundbegriffe der Informatik
Mit a in neuen Zustand, mit b zurück
Karlsruher Institut für Technologie
6/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
a
1
a
0
b
b
a
2
...(b|aa)
GBI — Grundbegriffe der Informatik
Mit b oder aa zurück zu 0
Karlsruher Institut für Technologie
6/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
a
1
a
b
0
b
b
3
a
2
b...
GBI — Grundbegriffe der Informatik
Mit b in neuen Zustand
Karlsruher Institut für Technologie
6/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
a
1
a
0
b
b
2
...(ba)*...
GBI — Grundbegriffe der Informatik
b
a
3
a
b
4
Mit b in neuen Zustand, mit a zurück
Karlsruher Institut für Technologie
6/9
Regulärer Ausdruck
Akzeptor
Konstruiere endlichen Akzeptor A so, dass
L(A) = h(a(ab)*(b|aa)|b(ba)*(a|bb))*i
a
1
a
b
0
b
b
a
b
2
...(a|bb)
GBI — Grundbegriffe der Informatik
3
a
a
b
4
Mit a oder bb zurück zu 0
Karlsruher Institut für Technologie
6/9
Endlicher Akzeptor
Rechtslineare Grammatik
Gegeben: Endlicher Akzeptor A = (Z , z 0 , X , f , F )
Gesucht: Rechtslineare Grammatik G mit L(G) = L(A)
Idee: G = (Z , X , z 0 , P ) so, dass
z 0 ⇒∗ x 0 x 1 . . . x n z
gdw.
f ∗ (z 0 , x 0x 1 . . . x n ) = z
z 0 ⇒∗ x 0 x 1 . . . x n
gdw.
f ∗ (z 0 , x 0x 1 . . . x n ) ∈ F
also
(z 1 → xz 2 ) ∈ P
gdw.
f (z 1 , x ) = z 2
(z → ϵ ) ∈ P
gdw. z ∈ F
Konkret: P = {z → x f (z, x ) | z ∈ Z , x ∈ X }
∪ {z → ϵ | z ∈ F }
GBI — Grundbegriffe der Informatik
Karlsruher Institut für Technologie
7/9
Endlicher Akzeptor
Rechtslineare Grammatik
Gegeben: Endlicher Akzeptor A = (Z , z 0 , X , f , F )
Gesucht: Rechtslineare Grammatik G mit L(G) = L(A)
Konkret: P = {z → x f (z, x ) | z ∈ Z , x ∈ X }
∪ {z → ϵ | z ∈ F }
Beispiel:
a
0
b
1
P = {0 → a1 | b2 | ϵ
b b
a
a
2
GBI — Grundbegriffe der Informatik
G = ({0, 1, 2}, {a, b}, 0, P ) mit
1 → a2 | b0
2 → a0 | b1}
Karlsruher Institut für Technologie
7/9
Zahl in Binärdarstellung um 1 inkrementieren
Eingabe: w ∈ {0, 1}∗
Ausgabe: u ∈ {0, 1}∗ so, dass Num2 (w ) + 1 = Num2 (u)
Beispiel: Num2 (100111) + 1 = Num2 (101000)
Lösungsidee: Niederwertige Bits bis zur ersten 0 kippen
0|0R, 1|1R
r
GBI — Grundbegriffe der Informatik
2|2L
1|0L
c0
0|1L
2|1L
h
Karlsruher Institut für Technologie
8/9
Turingmaschine
b|bR,
0|0R, 1|1R
b|bR,
0|0R, 1|1R
a|bR
z0
2|2R
a|aR
z1
2|1L
2|0L
w
a|aL
a|aL, b|bL,
0|0L, 1|1L
GBI — Grundbegriffe der Informatik
In zk außer bei 2 Kopf nach rechts
In z 0 bei a schreibe b, gehe in z 1
In z 1 bei a gehe in z 0
k in zk ist Anzahl gelesener a mod 2
In zk bei 2 schreibe k, gehe in l
In l Kopf nach links bis zum ersten a,
dann nach w, und halt bei 2
In w zum Wortanfang, dann in z 0
l
b|bL,
0|0L, 1|1L
Karlsruher Institut für Technologie
9/9
Turingmaschine
b|bR,
0|0R, 1|1R
b|bR,
0|0R, 1|1R
a|bR
z0
2|2R
a|aR
z1
2|1L
2|0L
w
a|aL
a|aL, b|bL,
0|0L, 1|1L
GBI — Grundbegriffe der Informatik
Kopf läuft von links nach rechts
Beginnend mit dem ersten a wird
jedes zweite durch b ersetzt
Bei gerader Anzahl von a wird 0 ans
Wortende geschrieben
Bei ungerader Anzahl 1
Falls kein a mehr auf dem Band,
Ende!
Ansonsten zurück zum Wortanfang
und alles noch einmal
l
b|bL,
0|0L, 1|1L
Karlsruher Institut für Technologie
9/9
Turingmaschine
b|bR,
0|0R, 1|1R
Eingabe w ∈ {a, b}
b|bR,
0|0R, 1|1R
a|bR
z0
2|2R
a|aR
z1
2|1L
2|0L
w
a|aL
a|aL, b|bL,
0|0L, 1|1L
GBI — Grundbegriffe der Informatik
l
b|bL,
0|0L, 1|1L
Anzahl der a halbiert sich bei jedem
Durchlauf
Ans Wortende wird geschrieben
1. Na (w ) mod 2
N (w )
2. b a2 c mod 2
N (w )
3. b a c mod 2
4
4. usw.
Binärdarstellung von Na (w ) wird
gespiegelt ans Wortende geschrieben
Am Ende steht auf dem Band:
b |w | R(Repr2 (Na (w ))).
Karlsruher Institut für Technologie
9/9

Download Report