Transcript
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
