Uebungblatt 5 Myhill Nerode Relation PDF

Preview

Summary

Übungsblatt zu Grundlagen der theoretischen Informatik Neu....

Description

Grundlagen der theoretischen Informatik SS 19 ¨ 5. Ubung Abgabe: 22.05.2019, 10:00 Uhr Aufgabe 1:

Myhill-Nerode-Relation I

4+4 Punkte

Bestimmen Sie f¨ ur die Sprachen L1 , L2 ⊆ {0, 1}∗ die Myhill-Nerode-Relationen. Repr¨asentiern Sie die L¨osungen jeweils durch die Angabe eines Repr¨asentantensystems und eine verbale ¨ Verifizieren Sie die Nicht¨aquivalenz der oder formale Beschreibung der Aquivalenzklassen. ¨ jeweils durch Zeugen. Repr¨sentanten der Aquivalenzklassen Geben Sie in beiden F¨ allen die Zuordnung aller W¨orter der L¨ange ≤ 3 zu den einzelnen ¨ Aquivalenzklassen an! a)

L1 = {w ∈ {0, 1}∗ | w enth¨alt einen Teilstring 110 }

b)

L2 = {w ∈ {0, 1}∗ | w enth¨alt keinen Teilstring 010 }

Aufgabe 2:

Myhill-Nerode-Relation II

5 Punkte

Sind X = {Xi | i ∈ I} und Y = {Yj | j ∈ J} zwei Partitionen der gleichen Menge X, dann nennt man X eine Verfeinerung von Y, wenn f¨ ur jedes i ∈ I ein j ∈ J existiert, so dass Xi ⊆ Y J . Sei A = (Q, Σ, δ, q0 , F ) ein DFA und L = L(A) die zugeh¨orige regul¨are Sprache. Beweisen Sie Folgendes anhand der entsprechenden Definitionen: a) Die Partition Σ∗ /RL von Σ∗ ist eine Verfeinerung der Partition {L, L wobei L das Komplement von L ist. b) Wenn L kein Block der Partition Σ∗ /RL ist, dann ist |F | ≥ 2. c) Wenn A ein Minimalautomat f¨ ur L ist, dann ist [ε]LR = {ε} genau dann, wenn es im Zustandsdiagramm von A f¨ ur keinen Zustand q eine gerichtete Kante von q nach q0 gibt. Hinweis: Was kann man in der Argumentation benutzen? ¨ der Relation RL als 1. In der Vorlesung wurde gezeigt, dass die Aquvalenzklassen Zust¨ande eines Minimalautomaten der Sprache L (nennen wir diesen Automaten AM R ¨ mit MR f¨ ur Myhill-Nerode) mit dem Anfangszustand [ε]RL und der Uberf¨ uhrungsfunktion δM R ([w]RL , a) = [wa]RL interpretiert werden k¨onnen. 2. Es wurde gezeigt, dass f¨ ur jeden DFA A, bei dem alle Zust¨ande von q0 aus erreichbar ¨ A≡ ein Minimalautomat von L(A) ist. Aus dem sind, der Aquivalenzklassenautomat Gezeigten folgt außerdem, dass jeder Minimalautomat A′ von L isomorph zu AM R ist, in dem Sinne, dass man ihn durch Umbenennung der Zust¨ande in AM R umwandeln kann.

weiter auf Seite 2

Aufgabe 3:

F¨ ur den DFA A aus der nebenstehenden Skizze soll ein Anfangsteil des Kleene-Algorithmus ausgef¨ urt werden. Bestimmen Sie insbesondere alle Ausdr¨ ucke der Form R0i,j aus der Initialisierung (in einer Tabelle 1 darstellen) sowie die Ausdr¨ ucke R12,3 und R3,2 aus der ersten Stufe und finden Sie f¨ ur beide einen m¨oglichst einfachen, a¨quivalenten Ausdruck. Aufgabe 4:

4 Punkte

Kleene-Algorithmus

Pumping-Lemma

0,1

1

1

2

0

3

1

0

3 + 3 Punkte

¨ verwenden wir noch einmal die Bezeichnung ϕ(x, w) f¨ ur die Wie in der ersten Ubung Anzahl der Vorkommen des Symbols x ∈ Σ in einem Wort w ∈ Σ∗ . Weisen Sie die Nicht-Regularit¨at der folgenden zwei Sprachen L, L′ ⊆ {a, b, c}∗ durch Verwendung des Pumping-Lemmas nach! L = { (ab)k ck | k ∈ N } L′ = {w ∈ {a, b, c}∗ | ϕ(a, w) = 2 und ϕ(b, w) = ϕ(c, w) + 1}...