1659 a2 - Einsendeaufgabe 2 SS2021 PDF

Preview

Summary

Grundlagen der Theoretischen Informatik 01659Einsendeaufgaben zur Kurseinheit 2Aufgabe 2. Konstruieren Sie eine DEA der folgende Sprache erkennt:L={w∈ {x,y}∗|wenthält nicht das Teilwortyxxy}.Begründen Sie kurz die Korrektheit Ihrer Konstruktion.Aufgabe 2. Geben Sie den Potenzautomaten zum folgenden ...

Description

Grundlagen der Theoretischen Informatik 01659 Einsendeaufgaben zur Kurseinheit 2 Aufgabe 2.1

Konstruieren Sie eine DEA der folgende Sprache erkennt: L = {w ∈ {x, y} ∗ | w enthält nicht das Teilwort yxxy}. Begründen Sie kurz die Korrektheit Ihrer Konstruktion. Aufgabe 2.2

Geben Sie den Potenzautomaten zum folgenden NEA an. b

a b 2

b

3

a

ε a, b 1

4

Aufgabe 2.3

Betrachten Sie die folgenden Sprachen über Σ= {0, 1} und geben Sie je einen regulären Ausdruck an, der diese Sprachen beschreibt: 1. Alle Wörter, die 010 nicht als Teilwort enthalten. 2. Alle Wörter mit einer ungeraden Anzahl von 1en. Beschreiben Sie Ihr Vorgehen kurz.

1

Aufgabe 2.4

Zeigen Sie, dass folgende Sprachen nicht regulär sind. (a) L1 = {a p | p ist Primzahl} n−} (b) L2 = {n ∈ {0, 1} ∗ | n = ← (c) L3 = {an bm | n , m} Aufgabe 2.5

Betrachten Sie den folgenden DEA über Σ= {a, b}. a a

1

a

2

3

b

b

b

a

6

a

5

b

4

b a, b

(a) Bestimmen Sie die äquivalenten Zustände mit Hilfe des TF-Algorithmus. (b) Geben Sie den kollabierten Automaten als Zustandsdiagramm an.

2...