Lösung 1

Theoretische Informatik
Prof. Dr. Juraj Hromkovič
Prof. Dr. Emo Welzl
http://www.ita.inf.ethz.ch/theoInf15
Departement Informatik
Lösungsvorschläge – Blatt 1
Zürich, 25. September 2015
Lösung zu Aufgabe 1
(a) Sei w = a1 a2 . . . am ein Wort mit m ≤ n verschiedenen Buchstaben. Dann sind
offensichtlich alle möglichen Teilwörter paarweise verschieden. Es bleibt also nur die
Anzahl der Teilwörter von w zu zählen. Für ein Teilwort der Länge i ≥ 1 gibt es
m − i + 1 mögliche Anfangspositionen in w, denn die Positionen m − i + 2, . . . , m
sind nicht möglich. Aufsummieren über alle möglichen Längen nichtleerer Teilwörter
ergibt insgesamt
m
X
(m − i + 1) = m · (m + 1) −
i=1
m
X
i = m · (m + 1) −
i=1
m · (m + 1)
m · (m + 1)
=
2
2
nichtleere Teilwörter. Dazu kommt noch das leere Wort, das Teilwort von jedem
Wort ist, insgesamt gibt es also
1+
m · (m + 1)
2
verschiedene Teilwörter von w.
(b) Wir zählen zunächst, wieviele Wörter der Länge n über {a, b, c} die Bedingung aus der
Aufgabenstellung nicht erfüllen. Dies sind alle diejenigen Wörter, die höchstens zwei
der Buchstaben enthalten. Es gibt 2n verschiedene Wörter, die nur die Buchstaben a
und b enthalten, denn für jede der n Positionen kann einer der beiden Buchstaben
gewählt werden. Analog gibt es 2n verschiedene Wörter, die nur a und c enthalten,
sowie 2n verschiedene Wörter, die nur b und c enthalten. Unter diesen 3 · 2n Wörtern
haben wir die Wörter an , bn und cn jeweils doppelt gezählt, also gibt es insgesamt
3 · 2n − 3 Wörter, die die Bedingung der Aufgabenstellung nicht erfüllen. Weil es
insgesamt 3n Wörter der Länge n über {a, b, c} gibt, haben wir insgesamt also
3n − 3 · 2n + 3
Wörter, die jeden der drei Buchstaben mindestens einmal enthalten.
Lösung zu Aufgabe 2
(a) Die Aussage ist korrekt, wir beweisen zwei Inklusionen.
({a}∗ {b}∗ )∗ ⊆ ({a, b}∗ )2 : Wir bemerken zunächst, dass {a, b}∗ die Menge aller
Wörter über Σ = {a, b} ist. Da auch ({a}∗ {b}∗ )∗ offenbar nur Wörter über
Σ = {a, b} enthält, folgt ({a}∗ {b}∗ )∗ ⊆ {a, b}∗ . Weil λ ∈ {a, b}∗ gilt, folgt auch
{a, b}∗ = {λ}{a, b}∗ ⊆ ({a, b}∗ )2 , also insgesamt ({a}∗ {b}∗ )∗ ⊆ ({a, b}∗ )2 .
({a, b}∗ )2 ⊆ ({a}∗ {b}∗ )∗ : Die Menge ({a, b}∗ )2 ist eine Teilmenge der Menge
{a, b}∗ aller Wörter über Σ = {a, b}. Deshalb reicht es aus zu zeigen, dass alle
Wörter aus {a, b}∗ in ({a}∗ {b}∗ )∗ enthalten sind.
Sei also x ∈ {a, b}∗ . Dann ist x = x1 . . . xn für ein n ∈ N und xi ∈ {a, b} für
alle 1 ≤ i ≤ n. Falls xi = a = aλ gilt, dann ist xi ∈ {a}∗ {b}∗ , da a ∈ {a}∗
und λ ∈ {b}∗ gilt. Analog folgt für ein xj = b = λb, dass xj ∈ {a}∗ {b}∗ . Damit
gilt xi ∈ {a}∗ {b}∗ für alle 1 ≤ i ≤ n, also x ∈ ({a}∗ {b}∗ )n und damit auch
x ∈ ({a}∗ {b}∗ )∗ .
(b) Die Aussage ist falsch, wie das folgende Gegenbeispiel zeigt. Wir bemerken zunächst,
dass jedes Wort in {a, b}2 genau zwei Buchstaben enthält, also sind in ({a, b}2 )∗ nur
Wörter gerader Länge enthalten. Es gilt a ∈ ({a}∗ {b}∗ )∗ , aber a ∈
/ ({a, b}2 )∗ , da a
ein Wort ungerader Länge ist.
(c) Auch diese Aussage ist falsch und wir können ein Gegenbeispiel angeben. Sei L1 = {λ}
und L2 = {a}∗ . Dann ist L2 − L1 = {a}+ , also L2 (L2 − L1 ) = {a}∗ {a}+ = {a}+ .
Andererseits ist (L2 )2 = {a}∗ {a}∗ = {a}∗ und L2 L1 = {a}∗ {λ} = {a}∗ , also (L2 )2 −
(L2 L1 ) = {a}∗ − {a}∗ = ∅.
Lösung zu Aufgabe 3
(a) Wir betrachten die Sprache L = {ab}∗ . Dann gilt Li = L für alle i ≥ 1. Wir zeigen
hierfür zwei Inklusionen. Sei i ≥ 1.
Li ⊆ L : Es gilt
x ∈ Li ⇐⇒ ∃x1 , . . . , xi ∈ L : x = x1 . . . xi
⇐⇒ ∃j1 , . . . , ji ∈ N : x = (ab)j1 . . . (ab)ji
⇐⇒ ∃j1 , . . . , ji ∈ N : x = (ab)j1 +...+ji
⇐⇒ ∃k ∈ N : x = (ab)k
⇐⇒ x ∈ L
L ⊆ Li : Sei x ∈ L. Es gilt x = xλi−1 , da xλ = x. Da λ = (ab)0 ist, folgt x =
x((ab)0 )i−1 . Da x ∈ L und (ab)0 ∈ L, ist x = x((ab)0 )i−1 ∈ Li .
Mit einem analogen Beweis kann man zeigen, dass jede Sprache der Form L = (L1 )∗
für eine beliebige Sprache L1 über einem beliebigen Alphabet die Bedingung L = Li
für alle i ≥ 1 erfüllt.
(b) Eine solche Sprache gibt es nicht. Angenommen, es gäbe eine nichtleere endliche
Sprache L 6= {λ}, so dass L2 = L.
Dann gäbe es ein Wort w ∈ L maximaler Länge, also |w| = max{|v| | v ∈ L}. Aus
L 6= {λ} folgt |w| ≥ 1. Da nach Annahme L2 = L, muss w2 ∈ L gelten. Dies ist
ein Widerspruch zu der Annahme, dass w ein Wort maximaler Länge in L ist, da
|w2 | > |w|.

Download Report