[FRAGE] - Bsp 1.4? [Archive] - Informatik-Forum.at

shirukuroodo

13-10-2007, 11:26

1.4 a) hab ich auch wahr.

Bei b) hab ich falsch, bin mir aber nicht sicher. Meine Begründung:
Angenommen wir haben eine Sprache L = {a,b}

L* (nach Def.) = {ε} U {a,b} U {aa,ab,ba,bb} U ...

L* = {wi | w element L, i >= 0} würde bedeuten:
= {a0, a1, a2, ..., b0, b1, ...}

Und die beiden sind eindeutig verschieden. Zumindest hab ich mir das so vorgestellt.

c) Da hab ich auch keine sehr elaborierte Antwort, ich hab einfach geschrieben, dass wenn z.B F keine reguläre Menge ist, die Vereinigung von L U F auch keine reguläre Menge mehr sein kann. Also ist die Aussage falsch.

Soviel zu meinen Lösungen, wie gesagt weiß ich nicht inwieweit sie stimmen, warte also auf weitere Vorschläge.

Hyphistos

14-10-2007, 13:51

Zu C: eine endliche Menge ist immer auch eine reguläre Menge, darum ist auch die Vereinigung regulär und der Satz somit richtig

Begründung: http://www.informatik-forum.at/showthread.php?t=41039

freeye

14-10-2007, 17:24

zu b.. w ist ein wort und kein zeichen.. also kann wenn L = {a,b} dann ist a,b das wort w, oder?

tonico

14-10-2007, 17:54

Zu C: eine endliche Menge ist immer auch eine reguläre Menge, darum ist auch die Vereinigung regulär und der Satz somit richtig

Begründung: http://www.informatik-forum.at/showthread.php?t=41039

Hmmm, also wenn ich jetzt z.B. die Menge der Postings der letzten 3 Tage hernehme, ist die dann auch regulär, wenn ja über welchem Alphabet.

Wenn eine Menge A1 über einem Alphabet Σ1 und eine Menge A2 über einem Alphabet Σ2 regulär ist, ist dann A1 U A2 über Σ1 regulär?

marioana

15-10-2007, 16:10

ist beispiel b nun wahr oder falsch??:confused:

ich würde sagen, ja es ist wahr:
da w^0 = {E} für n=0 und w^i unendlich ist für n>0.
somit können ja alle wörter in L* vorkommen, da w el L. ?!?
stimmt das so?

bei beispiel c würde ich auch wahr sagen - da eine reguläre menge L* und eine endliche menge F ja wieder eine reguläre menge ergeben muss, da ich ja bei L* unendlich viele möglichkeiten habe und somit auch L u. F unendlich ist - unabhängig von F. L bleibt ja trotzdem unendlich.
Bsp:
F={a,b} L*={c,d}
L*={E,c,d,ccd,ccccd....}
L u F = {a,b,c,d,ccd,ccccd,...}

wäre für eine antwort dankbar :druegg:

tonico

15-10-2007, 16:27

ist beispiel b nun wahr oder falsch??:confused:

ich würde sagen, ja es ist wahr:
da w^0 = {E} für n=0 und w^i unendlich ist für n>0.
somit können ja alle wörter in L* vorkommen, da w el L. ?!?
stimmt das so?

Ich würde sagen, nein es ist nicht wahr. Angenommen L = {0, 1}, dann ist das Wort w = 010101 nicht in der beschriebenen Menge, denn in dieser Menge sind nur Wörter die durch Potenzieren entstehen, und das Beispielwort w kann nicht durch Potenzieren eines Worts aus L entstehen.

bei beispiel c würde ich auch wahr sagen - da eine reguläre menge L* und eine endliche menge F ja wieder eine reguläre menge ergeben muss, da ich ja bei L* unendlich viele möglichkeiten habe und somit auch L u. F unendlich ist - unabhängig von F. L bleibt ja trotzdem unendlich.
Bsp:
F={a,b} L*={c,d}
L*={E,c,d,ccd,ccccd....}
L u F = {a,b,c,d,ccd,ccccd,...}

F = {e, 0, 1, 00, 01, 10, 11} ist regulär über dem Alphabet {0,1}, L = {a, aa} ist regulär über dem Alphabet {a}, aber F U L ist nicht regulär über dem Alphabet {0,1}, aber F U L regulär über {0, 1, a}. Also wenn man sagt eine Menge sei regulär, muss man auch dazusagen über welchem Alphabet denke ich.

axestr

15-10-2007, 17:34

F = {e, 0, 1, 00, 01, 10, 11} ist regulär über dem Alphabet {0,1}, L = {a, aa} ist regulär über dem Alphabet {a}, aber F U L ist nicht regulär über dem Alphabet {0,1}, aber F U L regulär über {0, 1, a}. Also wenn man sagt eine Menge sei regulär, muss man auch dazusagen über welchem Alphabet denke ich.

F = {e, 0, 1, 00, 01, 10, 11} ist eine Reguläre Menge. L = {a, aa} ist eine reguläre Menge (eine endliche Menge ist ja immer reguläre). Dann ist F u L auch eine reguläre Menge.

Ich kann ja für beide das Alphabet {e,0,1,2,3,1,b,c,d} verwenden ;-)

Lg, Axel.

axestr

15-10-2007, 17:44

Ich würde sagen, nein es ist nicht wahr. Angenommen L = {0, 1}, dann ist das Wort w = 010101 nicht in der beschriebenen Menge, denn in dieser Menge sind nur Wörter die durch Potenzieren entstehen, und das Beispielwort w kann nicht durch Potenzieren eines Worts aus L entstehen.

Wenn mein wort r=01 ist, dann ist r^3 = 01.01.01 = 010101.
Aber nim einfach mal 101. Das kann man nicht in der Form
L* = { w^i | w Element L, i>=0 } schreiben.
Es geht auch mit jedem beliebigem w=w1.w2, wo kein i mit w1^i=w2 oder umgekehrt existert. w1!=w2 reicht nicht, weil ja z.b. 01!=0101 ist, aber (01)^2=0101, und 010101=(01)^3.

Lg, Axel.

tonico

15-10-2007, 20:01

Wenn mein wort r=01 ist, dann ist r^3 = 01.01.01 = 010101.

Ich habe L mit {0, 1} angenommen, und wenn w in L dann kann w^i nicht 010101 sein, oder hast Du jetzt was anderes gemeint?

marioana

16-10-2007, 12:44

also ist 1.4 - c) doch richtig?

bei pt. b) würde mich interessieren, wie die wörter aussehen, die durch potenzieren entstehen.
denn wenn ich zb. L = {a,b} habe
und L besteht ja aus den potenzen von L^i.
jedoch wenn ich ein wort bilde, kann ich es ja immer aus den 2 kleinsten elementen bilden - sprich "a" und "b". somit komme ich ja dann eh auf alle wörter?!
liege ich da falsch? oder wird das von mir geschriebene mit der zweiten zeile der angabe wiederlegt?

denn was heißt w=w1....wn?

marioana

16-10-2007, 12:53

eine frage noch - habs denk ich noch nicht ganz verstanden:
was ist L^2 ?
wenn L = {0,1} ?

L x L = {0,1} x {0,1} = {00,01,10,11} ?

tonico

16-10-2007, 16:13

eine frage noch - habs denk ich noch nicht ganz verstanden:
was ist L^2 ?
wenn L = {0,1} ?

L x L = {0,1} x {0,1} = {00,01,10,11} ?

Ja so ähnlich, nur dass das kartesische Produkt (http://de.wikipedia.org/wiki/Kartesisches_Produkt) nicht als Verkettung von Symbolen definiert ist. Ich weiß jetzt nicht ob das was anderes ist, weil man ja eine Zeichenkette als n-Tupel auffassen kann, ich würd sicherheitshalber bei der Notation aus dem Script bleiben.

L^0 = {e}
L^1 = L
L^2 = L · L = {00, 01, 10, 11}
L^3 = L^2 · L = L · L · L = {000, 001, ..., 111}
...

tonico

16-10-2007, 16:22

also ist 1.4 - c) doch richtig?

Ja.

bei pt. b) würde mich interessieren, wie die wörter aussehen, die durch potenzieren entstehen.
denn wenn ich zb. L = {a,b} habe
und L besteht ja aus den potenzen von L^i.

L* ist die Vereinigung aller L^i mit i >= 0, meinst Du das?

jedoch wenn ich ein wort bilde, kann ich es ja immer aus den 2 kleinsten elementen bilden - sprich "a" und "b". somit komme ich ja dann eh auf alle wörter?! liege ich da falsch?

Ob mann alle Wörter die nur a oder b enthalten durch Verkettung von a und b erzeugen kann? Oder was ist hier die Frage?

marioana

16-10-2007, 16:49

Ja so ähnlich, nur dass das kartesische Produkt (http://de.wikipedia.org/wiki/Kartesisches_Produkt) nicht als Verkettung von Symbolen definiert ist. Ich weiß jetzt nicht ob das was anderes ist, weil man ja eine Zeichenkette als n-Tupel auffassen kann, ich würd sicherheitshalber bei der Notation aus dem Script bleiben.

L^0 = {e}
L^1 = L
L^2 = L · L = {00, 01, 10, 11}
L^3 = L^2 · L = L · L · L = {000, 001, ..., 111}
...

danke! ja ich meinte eh das mal (·) -zeichen nur fand ich es nicht und hab an stelle dem ein kleines x genommen ;)

marioana

16-10-2007, 16:52

Ja.

Ob mann alle Wörter die nur a oder b enthalten durch Verkettung von a und b erzeugen kann? Oder was ist hier die Frage?

genau, da ja L^1 {a,b} ergibt, kann ich ja mit a und b alle wörter zusammenstellen?
somit könne ich ja auch das wort w="aba" ohne weiteres erstellen?

tonico

16-10-2007, 17:19

genau, da ja L^1 {a,b} ergibt, kann ich ja mit a und b alle wörter zusammenstellen?
somit könne ich ja auch das wort w="aba" ohne weiteres erstellen?

Ähm ja, durch Verkettung. Alle Wörter die durch Verkettung von a und b erzeugt werden können sind in L*.

Fresh Prince

16-10-2007, 17:21

Hat wer da nun endgültige Lösungen für 1.4? Komm da irgendwie nicht weiter?
Lg

marioana

16-10-2007, 17:30

Ähm ja, durch Verkettung. Alle Wörter die durch Verkettung von a und b erzeugt werden können sind in L*.

ok! dann muss das beispiel ja meiner meinung richtig sein - oder was sagst du dazu? verketten darf man ja - somit komme ich auf alle wörter...

tonico

16-10-2007, 17:36

ok! dann muss das beispiel ja meiner meinung richtig sein - oder was sagst du dazu? verketten darf man ja - somit komme ich auf alle wörter...

Das Beispiel behauptet, dass L* = {w^i | w in L, i >=0}. Das ist leider falsch. Wenn L = {a, b} dann ist w entweder a oder b, und mit a^i oder b^i kann ich z.B. abba nicht erzeugen.

Edit: Ergänzung: Das Wort abba ist aber sicher in L*.

marioana

16-10-2007, 17:54

Das Beispiel behauptet, dass L* = {w^i | w in L, i >=0}. Das ist leider falsch. Wenn L = {a, b} dann ist w entweder a oder b, und mit a^i oder b^i kann ich z.B. abba nicht erzeugen.

Edit: Ergänzung: Das Wort abba ist aber sicher in L*.

das heißt w^i bedeutet es kann nur {a,aa,aaa,aaaa,....,b,bb,bbb,bbbb,...} wörter geben?
und das ist ungliech L*
stimmt das so?
sei L={a,b}
w^0 = {E}
w^1 = {a,b}
w^2 = {aa,bb}
w^3 = {aaa,bbb}
usw...

a.k

16-10-2007, 18:44

1.4. b) Ich glaube bei der zwiten Aussage fehlt das Leerwort!

axestr

16-10-2007, 19:17

1.4. b) Ich glaube bei der zwiten Aussage fehlt das Leerwort!

L*={w^i | w in L, i>=0}, d.h. epsilon = w^0 ist in L* mit w beliebig, i=0.

Lg, Axel.

marioana

16-10-2007, 19:35

das heißt w^i bedeutet es kann nur {a,aa,aaa,aaaa,....,b,bb,bbb,bbbb,...} wörter geben?
und das ist ungliech L*
stimmt das so?
sei L={a,b}
w^0 = {E}
w^1 = {a,b}
w^2 = {aa,bb}
w^3 = {aaa,bbb}
usw...

ist das nun so oder nicht?? :wave:

axestr

16-10-2007, 19:44

Ich hätte gesagt auch ab, abab, aabb, aabbaabb, .....
Denn z.B. kann ja w=w1w2 mit w1,w2 aus L sein, und dann ist
w^0 = e
w^1 = w1w2
w^2 = w1w2w1w2

Aber z.B. für aab wird man kein {w^i | w in L, i>=0} finden.

Lg, Axel, der vor lauter Bäumen bald den Wald nicht mehr sieht ... ;-)

P.S.: Setzt vorraus, dass aab nicht in L war!

marioana

16-10-2007, 20:15

tonico

16-10-2007, 20:16

ist das nun so oder nicht?? :wave:

Jup, so stehts im Skriptum SS07 auf S. 2.

Edit:
sei L={a,b}
w^0 = {E}
w^1 = {a,b}
w^2 = {aa,bb}
w^3 = {aaa,bbb}
usw...

Naja, nicht ganz, ich glaub du wolltest ca. das andeuten:

{w^i | w in L, i = 0} = {E}
{w^i | w in L, i = 1} = {a, b}
{w^i | w in L, i = 2} = {aa, bb}
{w^i | w in L, i = 3} = {aaa, bbb}

tonico

16-10-2007, 20:23

Ich hätte gesagt auch ab, abab, aabb, aabbaabb, .....
Denn z.B. kann ja w=w1w2 mit w1,w2 aus L sein, und dann ist
w^0 = e
w^1 = w1w2
w^2 = w1w2w1w2

Aber z.B. für aab wird man kein {w^i | w in L, i>=0} finden.

Aus L = {w1, w2} folgt nicht w = w1w2 in L, und w^i ebenfalls nicht in L, oder hast Du das anders gemeint?

a.k

16-10-2007, 21:40

was ich noch nicht verstanden habe L={a,b}
L*0 = Leerwort,
L*1 = {a,b},
L*2={aa,bb}
L*3={aaa,bbb}
L*4={aaaa,bbbb}

und bei w*1

L=Leerwort i=0
L={a,b} i=1
L={aa,bb} i=2
L={aaa,bbb} i=3
L={aaaa,bbbb} i=4

warum/wie kann w=ab sein?

tonico

16-10-2007, 21:48

was ich noch nicht verstanden habe L={a,b}
L*0 = Leerwort,
L*1 = {a,b},
L*2={aa,bb}
L*3={aaa,bbb}
L*4={aaaa,bbbb}

Ich verstehe nicht was z.B. L*2 heißen soll. Wenn L^2 gemeint ist, dann ist es {aa, ab, ba, bb}

und bei w*1

L=Leerwort i=0
L={a,b} i=1
L={aa,bb} i=2
L={aaa,bbb} i=3
L={aaaa,bbbb} i=4

warum/wie kann w=ab sein?

Ich versteh nicht genau was Du meinst, aber falls Du auf Posting um 19:16 bezug nimmst dann ist w = ab nicht in der Menge {w^i | w in L, i >=0}, sehr wohl aber in der Menge L*.

spjoe

16-10-2007, 22:44

Ja meiner meinung nach ist a) wahr weil die konkatination assoziativ ist

b) ist falsch weil in {a,b}* = auch {epsilon,a,b,aa,ab,ba,bb,....} enthalten wenn man aber sie wie in der angabe definiert gibt es nur {epsilon,a,b,aa,bb,.....}

c) sagen alles das es wahr würds jetzt nicht erklären können, ich glaub das halt gemeint ist egal welches alphabet bzw. elemente in der menge verwendet werden die regeln die auf der tafel gestanden sind bezüglich konkatination und vereinigungen stimmen (und anscheinen geht das mit einer endlichen menge immer)

tonico

16-10-2007, 23:47

c) sagen alles das es wahr würds jetzt nicht erklären können, ich glaub das halt gemeint ist egal welches alphabet bzw. elemente in der menge verwendet werden die regeln die auf der tafel gestanden sind bezüglich konkatination und vereinigungen stimmen (und anscheinen geht das mit einer endlichen menge immer)

F ist deswegen regulär weil F eine endliche Menge ist. Wenn L regulär ist und F regulär ist dann folgt per Definition (Skriptum SS07 Def. 1.10 b) dass L U F wieder regulär ist, laut Tutor ist das unabhängig vom Alphabet.

Was mich aber noch immer wurmt ist, dass ich nicht aus der Definition herauslesen kann, dass aus "F ist endlich" folgt "F ist regulär". Ich nehme z.B. eine endliche Menge mit einem einzigen Wort, das Wort sei die Darstellung der Zahl Pi im Dezimalsystem. Weil Pi unendlich viele Nachkommastellen hat ist das Wort ebenfalls unendlich lang und ich wüsste jetzt nicht wie ich dieses unendlich lange Wort regulär darstellen könnte.

a.k

17-10-2007, 01:44

Jetzt ist es mir klar. Danke dir tonico

mfg a.k!

axestr

17-10-2007, 09:40

Hallo!

Ich werde 1.4b aus meinem Leben streichen ;-)

Wenn ich sage Sigma ist {a,b}*, und L={a,ab}.
Dann ist aba in L*, aber aba nicht in {w^i | w in L, i>=0}

Beweis: wegen w=w1...wn und w1....wn in L kann ich sagen w1=ab, w2=a, also ist w=aba in in L^2, also in L*.

Wenn aber aba auch in {w^i | w in L, i>=0} wäre, dann müsste ich das Wort w^i in die Form w.w.w...w (i mal) zerlegen können, das geht aber nicht, da
weder a^i noch ab^i das Wort aba ergibt.

Passt das jetzt so?

Lg, Axel.

tonico

17-10-2007, 10:08