Theo Inf 3. Übungsblatt

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

1

Sunday, November 3rd 2002, 4:06pm

http://www-thi.informatik.uni-hannover.d…en/uebung03.pdf

---
zu Aufgabe 3:
mir fällt da irgendwie nicht mal ein Ansatz ein...

Was ist mit
L1 vereinigt L2 und
L1 Durchschnitt L2

gemeint? wie genau soll ich da das zeigen bzw. was soll ich wie einsetzen und wählen damit ich beweisen kann dass die wieder regulär sind?!

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

T2k

Erfahrener Schreiberling

Posts: 339

Date of registration: Oct 9th 2002

Location: da drüben, gleich dort.

Occupation: Warum? Hmm, weil ich sonst nix mit meiner Zeit anzufangen weiß :D

2

Monday, November 4th 2002, 1:42pm

würd ich auch gerne wissen

aber sag ma wie groß sind deine automaten in 1 und 2??

mein 1ster is 11 w's (=Wörter ???) lang/groß
der 2te ganze 5

T2k

Die zweithäufigste Todesursache eines Soldaten ist das Gewicht seines Rückentornisters ("http://olnigg.de/" Aug05/Nr120)

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

3

Monday, November 4th 2002, 4:22pm

also am ersten bastele ich noch im moment..
der von aufgabe 2 hat bei mir 3 zustände

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

4

Monday, November 4th 2002, 4:33pm

Quoted

Original von vier
zu Aufgabe 3:
mir fällt da irgendwie nicht mal ein Ansatz ein... Was ist mit
L1 vereinigt L2 und
L1 Durchschnitt L2

gemeint? wie genau soll ich da das zeigen bzw. was soll ich wie einsetzen und wählen damit ich beweisen kann dass die wieder regulär sind?!

Vorweg ein paar Begriffsklärungen, die vielleicht helfen:

Eine Sprache ist eine Menge von Wörtern. Demnach ergeben Mengenoperationen auf Sprachen (also z. B. Vereinigung und Durchschnittsbildung) wieder Sprachen.

Sprachen können z. B. durch Grammatiken, Automaten oder reguläre Ausdrücke definiert werden.

Hier ein paar Denkanstöße für einen anschaulichen Beweis in Aufgabe 3:

Gegeben sind zwei reguläre Sprachen L_1 und L_2. Also gibt es auch zu diesen Sprachen äquivalente endliche Automaten A_1 und A_2.

Zu zeigen ist nun, daß es je einen zu der Vereinigung von L_1 und L_2 und einem zum Durchschnitt von L_1 und L_2 äquivalenten endlichen Automaten gibt.

a) Vereinigung
Alle Wörter, die von A_1 oder A_2 akzeptiert werden, gehören zur Vereinigungsmenge von L_1 und L_2. Sind reguläre Sprachen unter der Vereinigung abgeschlossen, so gibt es einen Automaten A_3, der genau die Vereinigungsmenge von L_1 und L_2 akzeptiert.

b) Durchschnitt
Nur Wörter, die sowohl von A_1 als auch von A_2 akzeptiert werden, gehören zum Durchschnitt von L_1 und L_2. Sind reguläre Sprachen unter der Bildung des Durchschnitts abgeschlossen, so gibt es einen Automaten A_4, der genau den Durchschnitt von L_1 und L_2 akzeptiert.

Zu erklären ist also jeweils, wie man einen Automaten A_3 bzw. A_4 aus den Automaten A_1 und A_2 konstruiert.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

Go to the top of the page

mDev

Erfahrener Schreiberling

Posts: 282

Date of registration: Oct 10th 2002

Location: Hannover

Occupation: Wissenschaftlicher Mitarbeiter

5

Tuesday, November 5th 2002, 2:17pm

Quoted

Original von T2k
würd ich auch gerne wissen aber sag ma wie groß sind deine automaten in 1 und 2??

mein 1ster is 11 w's (=Wörter ???) lang/groß
der 2te ganze 5

mein erster is auch grad 11 zustände groß geworden... und mein zweiter hat 3.

Go to the top of the page

T2k

Erfahrener Schreiberling

Posts: 339

Date of registration: Oct 9th 2002

Location: da drüben, gleich dort.

Occupation: Warum? Hmm, weil ich sonst nix mit meiner Zeit anzufangen weiß :D

6

Tuesday, November 5th 2002, 5:57pm

hmm nur 3, hmm

du weist aber dass folgende wörter akzeptiert werden müssen?:
a^n°b, b°a^n mit n= 2k, k>=1 und
a^n°b°a^n mit n>=1

und das mit 3 zuständen

, da bin ich aber mal gespannt

aber vielleicht bin ich auch scho zu tief in lin.alg. drin das ich garnix mehr ralle :rolleyes:

T2k

Die zweithäufigste Todesursache eines Soldaten ist das Gewicht seines Rückentornisters ("http://olnigg.de/" Aug05/Nr120)

Go to the top of the page

mDev

Erfahrener Schreiberling

Posts: 282

Date of registration: Oct 10th 2002

Location: Hannover

Occupation: Wissenschaftlicher Mitarbeiter

7

Tuesday, November 5th 2002, 10:18pm

Quoted

Original von T2k
du weist aber dass folgende wörter akzeptiert werden müssen?:
a^n°b, b°a^n mit n= 2k, k>=1 und
a^n°b°a^n mit n>=1

ja in der tat, so war ja die aufgabenstellung...
also ich bin der meinung das meine lösung richtig ist! die gibts auf anfrage.

Go to the top of the page

Benjamin

Segelnder Alter Hase

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

8

Tuesday, November 5th 2002, 11:10pm

also meine Aufgabe 2 hat auch nur 3 Zustände.

und ich finde den Fehler einfach nicht... oder meine Aufgabe1-Lösung mit 7 Zuständen ist auch korrekt

Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

9

Tuesday, November 5th 2002, 11:20pm

Quoted

Original von metalhen
also meine Aufgabe 2 hat auch nur 3 Zustände.

und ich finde den Fehler einfach nicht... oder meine Aufgabe1-Lösung mit 7 Zuständen ist auch korrekt

Ich komme auf die selben Ergebnisse.

Also 7 Zustände bei Aufgabe 1 und 3 Zustände bei Aufgabe 2.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

Go to the top of the page

T2k

Erfahrener Schreiberling

Posts: 339

Date of registration: Oct 9th 2002

Location: da drüben, gleich dort.

Occupation: Warum? Hmm, weil ich sonst nix mit meiner Zeit anzufangen weiß :D

10

Wednesday, November 6th 2002, 10:46am

so aufg 2 hat jetzt ganze 2 zustände

liegt wohl daran das ich annehme das 0 ein vielfaches von 2 ist bzw durch 2 teilbar... und hmm aufg1 ma sehen wo ich zustände einsparen kann :rolleyes:

edit: so aufg1 sind jetzt auch 7...

T2k

Die zweithäufigste Todesursache eines Soldaten ist das Gewicht seines Rückentornisters ("http://olnigg.de/" Aug05/Nr120)

Go to the top of the page

Flu

Praktikant

Posts: 26

Date of registration: Oct 9th 2002

11

Wednesday, November 6th 2002, 9:09pm

Mein erster hat 10 Zustände der Zweite 3.

Go to the top of the page

Benjamin

Segelnder Alter Hase

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

12

Thursday, November 7th 2002, 1:29pm

so, nun bin ich ja mal gespannt auf die korrigierten Aufgaben...
Da es heute in der Vorlesung ja hieß, dass der Beweis von Nr.3 mittels Automaten ja nicht zulässig sei, da wir es noch nicht in der Vorlesung hatten...
tja, dann war der Tipp von cbe in der Übung am Montag auch ohne Erfolg..

Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

Go to the top of the page

KreiS

Senior Schreiberling

Posts: 701

Date of registration: Dec 17th 2001

Location: Hannover

Occupation: moep

13

Thursday, November 7th 2002, 5:30pm

ich frage mich warum der automat bei euch allen in der Aufgabe 1 7 zustände haben muss, hab den mit 6 gebastelt oder wieder etwas übersehen

gut das ich es an sich nur noch freiwillig bearbeiten kann

kaneda spring <-> ks <-> KreiS
"surrender is an option ...time to change everything" (ks '04)

Dakota-Indianer(Weisheit),"Wenn Du entdeckst, dass Du ein totes Pferd reitest, steig ab"

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

14

Thursday, November 7th 2002, 5:57pm

Quoted

Original von KreiS
ich frage mich warum der automat bei euch allen in der Aufgabe 1 7 zustände haben muss, hab den mit 6 gebastelt oder wieder etwas übersehen

So sollte es IMHO aussehen:

http://www.joachim-selke.de/images/forum/882_1.png

Und dieser Automat läßt sich auch nicht weiter minimieren (habe ich getestet).