Lösungen zu den Übungsblättern -- Automaten und formale ...

Automaten und formale Sprachen L?sungen zu den ?bungsbl?ttern

?bungsblatt 1

Aufgabe 1.1 (Sipser, exercise 1.3) M = ({q1, q2, q3, q4, q5}, {u, d}, , q3, {q3})

:

ud q1 q1 q2 q2 q1 q3 q3 q2 q4 q4 q3 q5 q5 q4 q5

u

d

d

d

d

d

q1

q2

q3

q4

q5

u

u

u

u

start

Aufgabe 1.2 (Sipser, exercise 1.6, part a-f, part k-n) a) {w|w beginnt mit 1 und endet mit 0}

1

Rami Swailem FH Gie?en-Friedberg

start 0

1

0

0

1

1

AfS L?sungen

0,1

b) {w|w enth?lt mindestens 3 Einsen }

0

0

0

0,1

start

1

1

1

c) {w|w enth?lt den Teilstring 0101}

1

0

start

s00

0

0,1

1 01 0 010 1 0101

1 d) {w|w ist mindestens 3 Zeichen lang und das 3. Zeichen ist 0}

0,1

start

0,1

0,1

0

1

0,1

e) {w|w beginnt mit 0 und hat ungerade L?nge oder beginnt mit 1 und hat gerade L?nge}

AFS_Loesungen.tex,v,1.1,January 2, 2007 at 14:45:20 CET

WS 06/07

Seite 2

Rami Swailem FH Gie?en-Friedberg

start

oder start

0

0,1

0,1

1

0,1

0,1

0

0,1

1

0,1

AfS L?sungen

f) {w|w enth?lt den Teilstring 110 nicht} 0

start

1

0

g) {, 0}

start

1

0,1

1

0

0 0,1

0,1 h) {w|w enth?lt eine gerade Anzahl Nullen oder genau 2 Einsen }

AFS_Loesungen.tex,v,1.1,January 2, 2007 at 14:45:20 CET

WS 06/07

Seite 3

Rami Swailem FH Gie?en-Friedberg

start

1

1

1

1

00

00

00

00

1

1

1

AfS L?sungen

i) Die leere Menge

1 0,1

start j) Alle W?rter au?er dem leeren Wort

start

0,1 0,1

Aufgabe 1.3 Es sei = {0, 1} und A, B seien Sprachen ?ber dem Alphabet mit

A = {w|w endet mit 1}

und

B = {w|w beginnt mit 1}. Beschreiben Sie, welche Sprachen sich mit den regul?ren Operationen A B, A B, A und B ergeben.

L?sung AB : AB : A : B :

AFS_Loesungen.tex,v,1.1,January 2, 2007 at 14:45:20 CET

WS 06/07

Seite 4

Rami Swailem FH Gie?en-Friedberg

AfS L?sungen

?bungsblatt 2

Aufgabe 2.1 In der Vorlesung wurden die Beweisideen vorgestellt, mit denen man zeigt, da? die Klasse der regul?ren Sprachen abgeschlossen bez?glich der Operationen Vereinigung, Konkatenation und Stern ist. Lesen Sie in dem Buch von Sipser nach, wie man die Konstruktion der betreffenden nichtdeterministischen endlichen Automaten formal aufschreibt.

Aufgabe 2.2 (Sipser, exercise, 1.7, part a-d, part g)

Geben Sie zu jeder der folgenden regul?ren Sprachen ?ber dem Alphabet {0, 1} das Zustandsdiagramm eines (Nichtdeterministischen) Endlichen Akzeptors mit der jeweils angegebenen Anzahl von Zust?nden an:

a) {w|w endet mit 00}, 3 Zust?nde

start

0

0

0,1 b) {w|w enth?lt den Teilstring 0101}, 5 Zust?nde

start

0

1

0

0,1 1

0,1

c) {w|w enth?lt eine gerade Anzahl Nullen oder genau2 Einsen }, 6 Zust?nde

0

0

1

1

start

0

0

1

1

AFS_Loesungen.tex,v,1.1,January 2, 2007 at 14:45:20 CET

WS 06/07

Seite 5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download