Zusatzaufgaben zur Theoretischen Informatik

Zusatzaufgaben zur Theoretischen Informatik
1. Diskutiere, ob die folgende Funktion f1: {0, 1,...., 9}* → {0, 1} total rekursiv ist. Es ist
f1(x) = 1 genau dann, wenn x das Anfangsstück der Dezimaldarstellung von π ist.
2. Diskutiere, ob die folgende Funktion f2: {0, 1,...., 9}* → {0, 1} total rekursiv ist. Es ist
f2(x) = 1 genau dann, wenn x als geschlossener Block in der Dezimaldarstellung von π
vorkommen.
3. Zeige, daß die Sprache f2-1(1) für die Funktion f2 aus Aufgabe 2 rekursiv aufzählbar ist.
4. Diskutiere, ob die folgende Funktion f3: {0, 1,...., 9}* → {0, 1} total rekursiv ist. Die Eingabe
x wird als Dezimalzahl interpretiert. Es ist f3(x) = 1 genau dann, wenn es in der
Dezimaldarstellung von π einen geschlossenen Block von mindesten x Siebenern gibt.
5. Eine Sprache L ist genau dann rekursiv, wenn es eine Turingmaschine gibt, die die Wörter
w ∈ L in kanonischer (lexikographischer) Reihenfolge auf ein Ausgabeband schreibt. Zeige
dies!
6. Eine Sprache L ist genau dann rekursiv aufzählbar, wenn es eine Turingmaschine gibt, die
die Wörter w ∈ L in beliebiger Reihenfolge auf ein Ausgabeband schreibt. Zeige dies!
7. Die Klasse der rekursiven und die Klasse der rekursiv aufzählbaren Sprachen sind
abgeschlossen gegen endliche Vereinigung. Gilt dies auch für unendliche Vereinigungen?
8. Ist die Klasse der rekursiven Sprachen oder die Klasse der rekursiv aufzählbaren
Sprachen gegen Differenzbildung abgeschlossen?
9. Für Reduktionen wird die Notation ≤ benutzt. Dies deutet zumindest auf eine partielle
Ordnung hin. Die Relation ≤ sollte also die Eigenschaften Reflexivität und Transitivität haben.
Zeige also:
a) L ≤ L für alle Sprachen L.
b) L1 ≤ L2 und L2 ≤ L3 ⇒ L1 ≤ L3
10. Das Problem, für eine Eingabe n, gegeben in Unärdarstellung, zu entscheiden, ob n
Primzahl ist, ist in P enthalten. Zeige dies!
11. Jede nichtdeterministische Turingmaschine läßt sich durch eine nichtdeterministische
Turingmaschine simulieren, die in jedem Schritt höchstens zwei zulässige
Nachfolgekonfigurationen hat und deren Rechenzeit nur um einen konstanten Faktor größer
als die der gegebenen Turingmaschine ist. Zeige dies!
12. Für Sprachen L1 und L2 über dem Alphabet Σ gilt: L1 ≤p L2, falls L1 ∈ P, L2 ≠ ∅ und L2 ≠ Σ*
ist. Zeige dies!
13. Wir behandeln das Münzwechselproblem. Eine Währung habe k verschiedenen
Münztypen mit den Werten n1 ≤ .... ≤ nk , wobei n1 = 1 ist. Für einen Betrag B soll die minimal
benötigte Münzzahl berechnet werden. Der Greedy Algorithmus berechnet die größtmögliche
Zahl der nk-Münzen, deren Wert B nicht übertrifft. Dann wird der Restbetrag mit den nk-1Münzen auf analoge Weise behandelt usw. Für die D-Mark Währung mit den Münzwerten 1,
2, 5, 10, 50, 100, 200, 500 ist der Greedy Algorithmus optimal (Beweis?), für eine FunnyWährung mit den Münzwerten 1, 5, 7 jedoch nicht. Der Betrag 10 läßt sich in zwei Münzen
wechseln, der Greedy Algorithmus braucht jedoch vier Münzen. Das Problem besteht nun
darin, für ein Münzsystem n1, ....., nk und einen Betrag B zu entscheiden, ob das System für
1
B funny ist, d.h. der Greedy Algorithmus nicht optimal ist. Zeige, daß dieses
Münzwechselproblem NP-vollständig ist.
14. Beschreibe den minimalen deterministischen endlichen Automaten über dem Alphabet
{0, 1}, der genau die Wörter akzeptiert, die höchstens ein Paar aufeinanderfolgender Nullen
und höchstens ein Paar aufeinanderfolgender Einsen enthalten.
15. Beschreibe den minimalen deterministischen endlichen Automaten über dem Alphabet
{0, 1}, der genau die Wörter akzeptiert, die 101 nicht als Teilwort enthalten.
16. Wie groß ist die Minimalzahl der Zustände eines deterministischen endlichen Automaten,
der alle durch a) 5, b) 6, c) 7 teilbaren Zahlen in Dezimaldarstellung, gegeben durch die
Ziffern in fallender Wertigkeit, akzeptiert?
17. Die Sprache L aller Wörter 0p, für die p eine Primzahl ist, ist nicht regulär, aber die
Sprache L* ist regulär. Zeige dies!
18. Charakterisiere alle regulären Sprachen über dem Alphabet {0}.
19. Für jede Sprache L über {0} ist L* regulär. Zeige dies!
20. Für die Anwendung des Pumping Lemmas kann die Option des Abpumpens
entscheidend sein. Zeige dies an einem Beispiel!
21. Für Sprachen L enthalte L1 alle Wörter a1, ...., an, für die es Buchstaben b1, ..., bn gibt, so
daß a1b1a2b2....anbn in L enthalten ist. Ist L1 stets regulär, wenn L regulär ist?
22. Für Sprachen L enthalte L2 alle Wörter, die zu L gehören, für die aber kein echtes Präfix
(echtes Anfangsstück) zu L gehört. Ist L2 stets regulär, wenn L regulär ist?
23. Ist die Klasse der rekursiven Sprachen gegen Konkatenation und Kleenschen Abschluß
abgeschlossen?
24. Rekursiv aufzählbare Sprachen können durch Chomsky-0 Grammatiken und durch
Turingmaschinen beschrieben werden. Gibt es große Unterschiede in der Länge der
Beschreibungen?
25. Wie kann die Länge der Ableitungsregeln von Chomsky-0 Grammatiken und Chomsky-1
Grammatiken beschränkt werden?
26. Beweise oder widerlege die folgenden Gleichungen für die regulären Ausdrücke L1, L2
und L3 :
a) (L1L2)L3 = L1(L2L3)
b) (L1*)* = L1*
c) (L1 + L2)* = L1* + L2*
d) (L1*L2*)* = (L1 + L2)*
27. Ist die Klasse der rekursiv aufzählbaren, kontextsensitiven oder regulären Sprachen
gegen Spiegelbildung (Wort in umgekehrter Reihenfolge) abgeschlossen?
28. Zeige den Abschluß der Klasse der regulären Sprachen gegen Vereinigung,
Konkatenation und Kleenschen Abschluß direkt mit Hilfe von regulären Grammatiken.
29. Konstruiere eine kontextfreie Grammatik für die Sprache aller Wörter 0i1j2k mit i≠j oder
j≠k.
2
30. Welche Sprache wird von der kontextfreien Grammatik mit den Regeln S → ε, S → 0S
und S → 0S1S erzeugt?
31. Kann jede eindeutige kontextfreie Grammatik in eine äquivalente eindeutige Grammatik
in Chomsky-Normalform transformiert werden?
32. Die Sprache aller Doppelwörter ww über dem Alphabet {0, 1} ist nicht kontextfrei. Zeige
dies!
33. Für Turingmaschinen M, die nicht im Anfangszustand stoppen, ist die Sprache aller
Konfigurationsfolgen, die Rechnungen der Turingmaschine darstellen, nicht kontextfrei.
Zeige dies!
34. Welche der folgenden Sprachen sind kontextfrei?
a) {oi1j | j = i2}
b) {oi1j | i = j oder i = 2j}
c) {0n1n2i | i ≠ n}
d) {0n1n! | n ≥ 1}
e) {0i1j2k | i + j = k}
35. Ist für jede kontextfreie Sprache auch die Spiegelsprache kontextfrei?
36. Sei G in Chomsky-Normalform und L die von G erzeugte Sprache.
a) Gib eine obere Schranke für die Länge eines längsten Wortes in L an, falls L endlich ist.
b) Gib eine obere Schranke für die Länge eines kürzesten Wortes in L an, falls L unendlich
ist.
c) Führen die Ergebnisse aus a) und b) zu einem effizienten Endlichkeitstest?
37. Ist es für eine kontextfreie Grammatik G und eine reguläre Grammatik G´ entscheidbar,
ob L(G) ⊆ L(G´) ist?
38. Entwerfe einen deterministischen Kellerautomaten für die Sprache aller 0-1-Wörter mit
gleich vielen Nullen wie Einsen, wobei jedes Präfix nicht mehr Einsen als Nullen enthält.
39. Welchem bekannten Maschinenmodell sind Kellerautomaten mit zwei Stacks äquivalent?
40. Entwerfe einen deterministischen Kellerautomaten, der genau die Wörter mit gleich
vielen Nullen wie Einsen akzeptiert.
41. Zeige, daß L = { anbmcn+m | n,m ≥0 } nicht regulär ist.
42. Zeige unter Verwendung von Abschlußeigenschaften, daß L = { ww | w ∈ {a,b}* } nicht
regulär ist.
43. Zeige unter Verwendung von Abschlußeigenschaften, daß L = { wwR | w ∈ {a,b}* } nicht
regulär ist.
44. Zeige, daß L = { anban | n ≥0 } nicht regulär ist.
3

Download Report