Beispiel 3.3

[willi.m]

Mein Vorschlag

[schrankk]

mit a) und b) bin ich natürlich einverstanden!!

aber bei c) sind mMn deine L1L2 und L2L1 nicht regulär! Man kann schon z.B. keinen DEA bilden, der am Anfang (Ende) die von dir gegebene nicht reguläre Sprache L1 akzeptiert... Und für jede reguläre Sprache lässt sich einen DEA konstruieren, oder?!

[willi.m]

ja bei c) bin ich mir nicht sicher

[phex]

bin auch für c = falsch, gegenbeispiel ähnlich wie willi.m

[bsoykal]

@willi.m

wie koennen wir wissen, ob {a*b*} regulaer ist oder was ist die Unterschied zwischen {a*b*} und {a^n b^n} ?

danke :)

[david.mihola]

@willi.m

wie koennen wir wissen, ob {a*b*} regulaer ist oder was ist die Unterschied zwischen {a*b*} und {a^n b^n} ?

danke :)

bin zwar nicht willi.m, aber hier die antwort:

{a*b*} bedeutet: zuerst beliebig viele a (evtl. auch gar keines) und dann beliebig viele b (evtl. auch gar keines); es müssen aber nicht gleich viele a wie b sein.

{a^nb^n | n >= 0} bedeutet: zuerst eine beliebige anzahl von a (evtl. auch gar keines), und danach genau gleich viele b (das n ist also in beiden fällen dasselbe). {a^nb^m | n,m >= 0} wäre equivalent zu {a*b*}.

lg, david

ach so, und {a*b*} ist deshalb regulär, weil du es durch stern und konkatenation (in dieser reihenfolge) aus {a} und {b} konstruieren kannst. also, zuerst „sternst“ du {a} und {b} und dann konkatenierst du {a}* und {b}*.

[KatzeImSack]

Zu c:

Folien S. 44: reguläre Sprachen sind abgeschlossen gegenüber verkettung --> somit müsste die behauptung RICHTIG sein, nichnich?

Grüße!

[jperl]

Zu c:

Folien S. 44: reguläre Sprachen sind abgeschlossen gegenüber verkettung --> somit müsste die behauptung RICHTIG sein, nichnich?

Grüße!

das schließt jedoch nicht aus, dass nicht auch eine reguläre und eine nicht reguläre sprache miteinander verkettet wieder eine reguläre sprache ergeben.

somit kannst du mit dieser aussage nicht drauf schließen, dass L1 regulär ist.

jperl

[bsoykal]

L1 ={a,b}* und
L2 ={a^n b^n l n>=0}

Ich weiss, dass L1 regulaer und L2 nicht regulaer sind.
Aber kann jemand mir erklaeren, warum L1L2 und L2L1 regulaer sind ?

[schrankk]

L1 ={a,b}* und
L2 ={a^n b^n l n>=0}

Ich weiss, dass L1 regulaer und L2 nicht regulaer sind.
Aber kann jemand mir erklaeren, warum L1L2 und L2L1 regulaer sind ?
mMn sind L1L2 und L2L1 doch nicht regulär. Und die Aussage c) sollte eigentlich WAHR sein. Da in jedem Fall die neue Sprache wird mittels Verkettung gebildet (L2L1, L1L2), d.h. am Ende (Anfang) einer reg. Sprache wird einfach nur noch eine andere angehängt, die reg. sein sollte... Tut mir Leid, einen vernünftigen Beweis habe ich eh selbst noch nicht!

[schrankk]

ich würd so z.B. sagen: nehmen wir an, L1 ist nicht regulär. Dann lässt es sich keinen DEA zu L1 konstruieren (Satz in Folien auf Seite 41). Da L1L2 regulär sein sollte, lässt es sich einen DEA zu dieser Sprache konstruieren. Es gibt die eindeutige Vorgehensweise, wie man die Verkettung von zwei reg Sprachen durch einen DEA repräsentiert, und dort sollen es zwei DEA gegeben sein, was nicht der Fall ist, da zu L1 keinen DEA gebildet werden kann... :)

[bsoykal]

Also du meinst;

L1 regulaer & L2 nicht regulaer

=> bei der konkatenation koennen wir niemals eine reg. Sprache bekommen oder ?

[willi.m]

hatte n falsches bsp gewählt...
hier mal mit dem versuch

L2 ist die leere sprache

the empty language Ø is a regular language. (wikipedia)

If one of those languages is the empty language - the language with no strings, not even the empty string - then the concatenation is also the empty language. (Quelle (http://blogs.msdn.com/ericlippert/archive/2005/11/25/regular-expressions-from-scratch-part-three-concatenation.aspx))

sodala.

[schrankk]

Good job, willi.m!! :thumb:

[jperl]

kann mir jemand bei 3.3b näher erläutern warum die aussage richtig ist?

jperl

#edit
siehe satz 1.35 skriptum.

[War10ck]

jperl

#edit
siehe satz 1.35 skriptum.

kannst mal posten bin noch nicht dazugekommen es zu kaufen

thx a lot

[jperl]

naja im besagten satz 1.35 steht, dass man eine reguläre sprache durch einen endlichen automaten beschreiben kann.
diesen automaten kann man dann auch so umdrehen, dass er für L^r gilt und somit ist bewiesen, dass die sprache auch regulär ist.

jperl

[schrankk]

In meinem Skriptum (Version März 2008) steht sogar, dass "Reguläre Sprachen gegenüber Spieglung abgeschlossen sind"