close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Menuplan

EinbettenHerunterladen
Humboldt-Universität zu Berlin
Prof. Dr. Klaus Reinhardt
Einführung in die Theoretische Informatik
20. Oktober 2014
Übungsblatt 2
Besprechung der mündlichen Aufgaben am 27.10.–30. 10. 2014
Abgabe der schriftlichen Lösungen bis 15:10 Uhr am 3. 11. 2013
Aufgabe 11
Seien A, B, C Sprachen. Zeigen oder widerlegen Sie:
❻
❻
2
❻
(a) ❽➌a➑❻ ➌b➑❻ ➂ ❽➌a, b➑❻ ➂ , (b) ❽➌a➑❻ ➌b➑❻ ➂ ❽➌a, b➑2 ➂ ,
(c) A✔ AA❻ ,
(d) A❼B ✾ C ➁ ❜ AB ✾ AC,
(e) A❼B ✽ C ➁ AB ✽ AC,
Aufgabe 12
(mündlich)
(mündlich)
(f) A❼B ✾ C ➁ AB ✾ AC.
(3+2 Punkte)
mündlich
Für eine Sprache L seien
min❼L➁ ➌x ❃ L ❙ kein Wort y ❃ L ist echtes Präfix von x➑
5 Punkte
und
max❼L➁ ➌x ❃ L ❙ x ist kein echtes Präfix eines Wortes y ❃ L➑.
L heißt präfixfrei, falls kein Wort in L echtes Präfix eines anderen Wortes in L ist.
(a) Charakterisieren Sie die Präfixfreiheit mit Hilfe des min-Operators.
(b) Zeigen Sie, dass die Aussagen L max❼L➁ und L min❼L➁ äquivalent sind.
(c) Zeigen Sie, dass die Klasse REG unter dem min-Operator abgeschlossen ist,
d. h. für L ❃ REG folgt min❼L➁ ❃ REG.
Aufgabe 13
5+10 Punkte
Sei L ❜ Σ❻ eine reguläre Sprache. Zeigen Sie, dass dann auch die folgenden Sprachen
regulär sind, indem Sie beschreiben wie Sie aus einem beliebigen DFA für L einen
DFA (oder NFA) für diese Sprachen konstruieren. Begründen Sie jeweils auch die
Korrektheit des von Ihnen konstruierten Automaten.
(a) prefix❼L➁ ➌x ❃ Σ❻ ❙ ➜y ❃ Σ❻ ✂ xy ❃ L➑,
(mündlich)
(b) LR ➌xR ❙ x ❃ L➑,
(mündlich)
(xR bezeichnet das gespiegelte Wort, z.B. abcdR dcba)
(c) suffix❼L➁ ➌x ❃ Σ❻ ❙ ➜y ❃ Σ❻ ✂ yx ❃ L➑,
(2 Punkte)
✔
(d) L ,
(3 Punkte)
*(e) cycle❼L➁ ➌vu ❃ Σ❻ ❙ uv ❃ L➑,
(4 Zusatzpunkte)
*(f) L⑦2 ➌x ❃ Σ❻ ❙ ➜y ❃ Σ❻ ✂ xy ❃ L, ❙x❙ ❙y ❙➑.
(6 Zusatzpunkte)
Hinweis: Mit * markierte Aufgaben haben einen erhöhten Schwierigkeitsgrad.
Aufgabe 14 Betrachten Sie die Sprachen
10 Punkte
❻
❻
A ➌u ❃ ➌a, b➑ ❙ u endet mit b➑ und B ➌v ❃ ➌a, b➑ ❙ #a ❼v ➁ ist ungerade➑.
(a) Geben Sie für A und B jeweils einen DFA mit 2 Zuständen an.
(2 Punkte)
(b) Konstruieren Sie aus diesen DFAs mit dem Verfahren aus der Vorlesung einen
NFA N für das Produkt L AB.
(3 Punkte)
(c) Konstruieren Sie aus N einen NFA N ➐ für die Sternhülle L❻ von L mit dem
Verfahren aus der Vorlesung.
(5 Punkte)
Aufgabe 15
mündlich
Ein ENFA (extended NFA) ist wie ein NFA ein 5-Tupel N ❼Z, Σ, δ, S, E ➁, wobei δ
die Form
δ ✂ Z ✕ Σ✔
P
Z➁
❼
hat und ➌❼z, w➁ ❙ δ ❼z, w➁ ① ❣➑ endlich ist. Der Zustandsgraph von N hat also nur
endlich viele Kanten, die mit Wörtern w ❃ Σ✔ beschriftet sind.
(a) Definieren Sie die von einem ENFA N erkannte Sprache formal.
(b) Zeigen Sie, dass bei Verzicht auf die Bedingung „➌❼z, w➁ ❙ δ ❼z, w➁ ① ❣➑ ist
endlich“ jede Sprache L ❜ Σ❻ von einem ENFA erkannt wird.
(c) Zeigen Sie, dass ➌L❼N ➁ ❙ N ist ein ENFA➑ REG ist, indem Sie aus einem
beliebigen ENFA einen äquivalenten NFA konstruieren und umgekehrt.
(d) Zeigen Sie, dass ➌L❼N ➁ ❙ N ist ein ENFA➑ REG auch gilt, wenn man Σ✔ durch
Σ❻ ersetzt, d.h. δ ✂ Z ✕ Σ❻ P ❼Z ➁.
(optional)
Aufgabe 16
mündlich
Sei L1 ❜ ➌a, b➑❻ die Sprache der Wörter, die aba als Teilwort enthalten.
(a) Geben Sie einen NFA N für L1 an und zeigen Sie, dass L❼N ➁ L1 ist.
(b) Konstruieren Sie den zu N gehörigen Potenzmengenautomaten.
(c) Geben Sie reguläre Ausdrücke für L1 und für L1 an.
Gegeben sei nebenstehender NFA N .
10 Punkte
(a) Geben Sie die Sprache L❼N ➁ an.
(b) Wandeln Sie den NFA N mittels der in der Vorlesung vor2
gestellten Potenzmengenautomatenkonstruktion in einen
a
DFA M um, wobei Sie hier eventuell überflüssige Zustänb
de nicht weglassen sollen.
3
(c)
Geben Sie die in M nicht erreichbaren Zustände an.
b
b (d) Geben Sie reguläre Ausdrücke für L❼N ➁ und L❼N ➁ an.
Aufgabe 17
a
b
1
b
Document
Kategorie
Seele and Geist
Seitenansichten
13
Dateigröße
198 KB
Tags
1/--Seiten
melden