Beispiel 1.5

[Silent_Bob]

Hi!
Meine Ideen für Bsp. 1.5
Bin bei der Korrektheit der regulären Ausdrücke nicht ganz sicher:

\Sigma = \lbrace\underline{0},\underline{1}\rbrace

a) \mathcal L = \lbrace \mathit w \in \Sigma^* \mid \mathit w ohne \underline{00},\underline{11}\rbrace \to \lbrace\varepsilon\mid\underline{1}\mid\underline{ 0} \rbrace \mid\lbrace\underline{10}\mid\underline{01} \rbrace ^{*} da nur die Worte \varepsilon,0,1,10,01,101,010,1010,...., erlaubt sind.

b) \mathcal L = \lbrace \mathit w\in\Sigma^*\mid \mid\mathit w\mid = 2n+1, n \geq 0 \rbrace \to \forall \mathit w \in \Sigma := \lbrace a_i\rbrace^{2n+1} \mid n \geq 0 also nur Wörter mit ungerader Länge.

c) \mathcal L = \lbrace \mathit{awa} \mid \in \Sigma, \mathit w \in \Sigma^*\rbrace \to \mathit w = \varepsilon \mid \lbrace\underline{1} \mid \underline{0}\rbrace^* a = 1 \mid 0

mfg

[tuempl]

a) \mathcal L = \lbrace \mathit w \in \Sigma^* \mid \mathit w ohne \underline{00},\underline{11}\rbrace \to \lbrace\varepsilon\mid\underline{1}\mid\underline{ 0} \rbrace \mid\lbrace\underline{10}\mid\underline{01} \rbrace ^{*} da nur die Worte \varepsilon,0,1,10,01,101,010,1010,...., erlaubt sind.

ich glaube, dass \lbrace\underline{10}\mid\underline{01} \rbrace ^{*} auch 1001, 0110, ... - also kombinationen der beiden elemente miteinander beinhaltet, was ja dann falsch wär. bin mir aber nicht sicher.


b) \mathcal L = \lbrace \mathit w\in\Sigma^*\mid \mid\mathit w\mid = 2n+1, n \geq 0 \rbrace \to \forall \mathit w \in \Sigma := \lbrace a_i\rbrace^{2n+1} \mid n \geq 0 also nur Wörter mit ungerader Länge.


ist das Reguläre darstellung? mein vorschlag:
({0}u{1}) ({0,1}{0,1})*


c) \mathcal L = \lbrace \mathit{awa} \mid \in \Sigma, \mathit w \in \Sigma^*\rbrace \to \mathit w = \varepsilon \mid \lbrace\underline{1} \mid \underline{0}\rbrace^* a = 1 \mid 0


Mein vorschlag:
{0,1}+ ({0}u{1})

[Clyde]

Vorsicht bei c), a muss sowohl vor w als auch nach w das gleiche Zeichen sein (Palindrom)!

[Silent_Bob]

ich glaube, dass \lbrace\underline{10}\mid\underline{01} \rbrace ^{*} auch 1001, 0110, ... - also kombinationen der beiden elemente miteinander beinhaltet, was ja dann falsch wär. bin mir aber nicht sicher.

Ja stimmt, da hast du glaub ich recht...
2.Vorschlag: \lbrace\varepsilon\mid\underline{1}\mid\underline{ 0}\rbrace\mid\lbrace\underline{10}\rbrace^*\mid \lbrace\underline{01}\rbrace^* also entweder: \varepsilon,1,0,10,01,101010...,010101...,


ist das Reguläre darstellung? mein vorschlag:
({0}u{1}) ({0,1}{0,1})*sieht ziemlich gut aus.... bei (\lbrace\underline{0}\rbrace\cup\lbrace\underline{ 1}\rbrace) bin ich mit nicht sicher....


Mein vorschlag:
{0,1}+ ({0}u{1})erklärst du bitte genauer wie du darauf kommst...

[tuempl]

Vorsicht bei c), a muss sowohl vor w als auch nach w das gleiche Zeichen sein (Palindrom)!

danke für den hinweis mit dem gleichen zeigen. aber ich versteh nicht, dass es ein palindrom sein muss, meiner ansicht nach muss nur der erste und letzte buchstabe gleich sein, oder?

[Clyde]

Das stimmt - ist natürlich nur garantiert ein Palindrom für |w| < 2 :D

Aber so wird ein Palindrom ja gebildet, indem man Schritt für Schritt an ein Zeichen oder das Leerwort links und rechts ein (gleiches) Zeichen anhängt.

[manül]

\lbrace\varepsilon\mid\underline{1}\mid\underline{ 0}\rbrace\mid\lbrace\underline{10}\rbrace^*\mid \lbrace\underline{01}\rbrace^*
Hab ich auch so. Wenn auch mit Vereinigung definiert, was aber eh das selbe ist.

c) (\lbrace\underline{0}\rbrace\lbrace\underline{0}, \underline{1}\rbrace*\lbrace\underline{0}\rbrace) \cup (\lbrace\underline{1}\rbrace\lbrace\underline{0}, \underline{1}\rbrace*\lbrace\underline{1}\rbrace)

[Bianconeri]

Zu a: Mit der Lösung {epsilon | 1 | 0} | {1 0}* | {0 1}* sind doch nur Wörter mit |w| = 1 oder |w| = gerade möglich. Es ist allerdings z.b. unmöglich 010 zu bilden.

Meine Idee wäre: {0, epsilon} {1 0}* {1, epsilon}

Zu b würde ich sagen (ausgebessert): {0, 1} {10, 01, 00, 11}*

Zu c: Habe ich wie manül

[manül]

Zu a: Mit der Lösung {epsilon | 1 | 0} | {1 0}* | {0 1}* sind doch nur Wörter mit |w| = 1 oder |w| = gerade möglich. Es ist allerdings z.b. unmöglich 010 zu bilden.

Meine Idee wäre: {0, epsilon} {1 0}* {1, epsilon}
hast m.E. recht. sehr schöne Lsg.

Zu b würde ich sagen: {0, 1}+ {10, 01}*
wie machst mit deiner Lsg "011" ? :)

[Bianconeri]

wie machst mit deiner Lsg "011" ? :)

Mh das ist eigentlich schon machbar aber ich merk grad so kann ich ja auch Wörter mit gerader Länge bilden. Vielleicht dann doch eher {0, 1} {01,10,00,11}*

[manül]

Vielleicht dann doch eher {0,1}{01,10,00,11}*
was das selbe ist wie: {0,1}({0,1}{0,1})* :)

[kodiacc]

dieses | als notation für oder.. gilt das? das sehe ich so nirgendswo auf den folien oder im skriptum?! oda bin ich blind?
oder ist das folgende äquivalent {a,b} <=> {a|b}

[david.mihola]

Zu a: ...
Meine Idee wäre: {0, epsilon} {1 0}* {1, epsilon}


Nur um sicherzugehen:

Du meinst

\lbrace \underline{0}, \eps \rbrace \lbrace \underline{10} \rbrace* \lbrace \underline{1}, \eps \rbrace

und nicht

\lbrace \underline{0}, \eps \rbrace \lbrace \underline{1},\underline{0} \rbrace* \lbrace \underline{1}, \eps \rbrace

oder?

Aber: die Angabe sagt doch nur, dass die Wörter 00 und 11 nicht vorkommen dürfen. Durch die rekursive Definition der regulären Mengen heißt das dann wahrscheinlich auch, dass Konkatenationen davon auch nicht vorkommen dürfen, wie z. B. 0000, 0011.

Aber da die Wörter 01 und 10 vorkommen dürfen, müssten doch auch deren Konkatenationen vorkommen dürfen, auch wenn dann Dinge entstehen wie 1001 oder 010110, wo also über die ursprünglichen Wortgrenzen hinweg zwei 0er oder zwei 1er zusammenkommen.

Das wäre dann also

\lbrace \underline{0}, \underline{1}, \underline{10}, \underline{01} \rbrace*

Oder heißt die Angabe wirklich, dass in keinem Wort zwei 0er oder zwei 1er nebeneinander liegen dürfen?

LG, David

EDIT: OK, war vielleicht doch alles ein Blödsinn, was ich da geschrieben hab; die Angabe lautet ja tatsächlich „w enthält weder 00 noch 11“ und nicht „w ist weder 00 noch 11“. Und selbst wenn, wäre mein Vorschlag trotzdem falsch, weil man mit dem ja wieder 00 und 11 bilden kann... du scheinst also recht zu haben.

[Bianconeri]

@kodiacc
Ich weiß nicht ob es in der LVA so erlaubt ist aber prinzipiell kann man | sowohl als oder als auch äquivalt zu {a, b}, was ja eigentlich auch ein oder ist, verwenden.

@david.mihola
Ja, ohne den Beistrich natürlich.

[david.mihola]

@david.mihola
Ja, ohne den Beistrich natürlich.

OK. Du hattest es ja eh ohne Beistrich, aber das Leerzeichen dazwischen hat mich verunsichert...

LG, David

[zidane]

@manül

Kannst kurz erläutern wie du auf die Antwort (c) kommst

[manül]

Kannst kurz erläutern wie du auf die Antwort (c) kommst
a muss ein Symbol aus dem Alphabet sein und muss am Anfang und Ende jedes möglichen Wortes stehen. Dazwischen können Symbole aus Sigma* (={0,1}*) sein. Das Alphabet besteht aus dem Symbol 0 und 1, also meine 2 Möglichkeiten/Kombinationen miteinander vereinigt.

[Guybrush333]

genial!
wie kommst du darauf???

[bsoykal]

Fuer 1.5 c )Es muss nicht ein Palindrom sein. Beginn mit a dann irgend ein wort w und am ende wieder ein a . :)

[Al Kupone]

ich bin auch der meinung, dass manüls ergebnis richtig ist. w besteht aus dem stern-operator von sigma, dh.: irgendeine mischung aus dem symbolen. wichtig ist nur das a, das sowohl am anfang,wie am ende sein soll.

kann mir einer sagen, wie ich die coolen mathe-symbole einbauen kann?

[rgta]

Hab die drei Sprachen als DEA dargestellt. Sollte so stimmen, oder is jemand anderer Meinung? ^^

[HTM]

Hat da jemand die richtigen Lösungen?
a und c habe ich noch nicht ganz..