Beispiel 1.1

[Silent_Bob]

Hi!

Ich poste mal meine Lösung:

a. (\lbrace \underline{0} \rbrace \lbrace \underline{10} \rbrace^*\lbrace\underline{1}\rbrace) \cup \lbrace \varepsilon\rbrace = \lbrace\underline{0} \underline{10}^{n}\underline{1}\mid n\geq 0,\varepsilon\rbrace
Ist sicher nicht formal korrekt ausgedrückt, aber ich hoffe es kommt raus was gemeint ist.

b. \lbrace\underline{a}\rbrace\lbrace\rbrace \cup \lbrace\rbrace^* = \lbrace\rbrace \cup \lbrace\varepsilon\rbrace = \lbrace\varepsilon\rbrace

c. \lbrace\rbrace^*\lbrace\underline{a}\rbrace^+ \lbrace\rbrace = \lbrace\varepsilon\rbrace \lbrace\rbrace = \lbrace\underline{a}\rbrace^+

d. (\lbrace\underline{11}\rbrace \cup \lbrace\underline{111}\rbrace)^* = \lbrace\underline{11},\underline{111}\rbrace^* = \lbrace\underline{1}^n \mid n \geq 2 ,\varepsilon\rbrace = \lbrace\underline{1}\rbrace^* - \lbrace\underline{1}\rbrace
Hier bin ich mir wieder nicht sicher was die Notation betrifft...

e.
\lbrace\underline{00}\rbrace^* \cup (\lbrace\underline{0}\rbrace\lbrace\underline{00} \rbrace ^*) = \lbrace\varepsilon,\underline{00},\underline{0000} ,\underline{000000},...\rbrace \cup \lbrace\varepsilon,\underline{0},\underline{000}, \underline{00000},...\rbrace also \lbrace\underline{0}^{2n} \mid n \geq 0\rbrace \cup \lbrace\underline{0}^{2n-1} \mid n \geq 2\rbrace = \lbrace\underline{0}\rbrace^*

f. \lbrace\underline{a}\rbrace^* \cap \lbrace\underline{a},\underline{b}\rbrace^+ = \lbrace\underline{a}\rbrace^+

[snax]

Hier meine Lösungen hoffentlich liege ich nicht völlig daneben... die stimmen mit deinen eh fast überein aber so eine Notation wie du sie benutzt hab ich bei den Lösungen der Vorjahre nie gesehen... heißt aber nicht das es falsch ist.

a) ({0}{10}*{1}) u {eps} = ({10}{10}*) u {eps} = {10}+ u {eps} = {10}* (da bin ich seeehr unsicher ist auch etwas aus der Luft gegriffen)

b) {a}{} u {}* = {}u{eps} = {eps}

c) {}*{a}+{} = {eps}{a}+{} = {a}*{} = {} (hier verstehe ich deine Vorgehensweise nicht ganz...)

d) ({11} u {111})* = {11,111}* (vereinfachst du hier noch weiter?)

e) {00}* u ({0}{00}*) = {00}* u {0}* = {0}*

f) {a}* n {a,b}+ = {a}+

[gonzo69]

hmmm

zu b) glaub das kann man so verstehen {a_} {} u {}*
{a_} {} = {} ... weil irgendwas verkettet mit einer leeren menge ist immer die leere menge
dann bleibt {} u {}* und soweitich glaub/weiß heißts auch irgendwas vereinigt mit einer leeren menge ist wieder eine leere menge, also:
{a_} {} u {}* = {}

zu c) is glaub ich gleiches prinzip wie oben {}* {a_} {}
{a_} {} = {}, dann bleibt {}* {} = {}, also
{}* {a_} {} = {}

mein senf dazu

[Silent_Bob]

a) ({0}{10}*{1}) u {eps} = ({10}{10}*) u {eps} = {10}+ u {eps} = {10}*

Hier bin ich mir auch nicht sicher was das Ergebnis angeht.


c) {}*{a}+{} = {eps}{a}+{} = {a}*{} = {} (hier verstehe ich deine Vorgehensweise nicht ganz...)


\lbrace\rbrace^* wird zu \varepsilon Ergebnis ist bei mir dann \lbrace\varepsilon\rbrace


d) ({11} u {111})* = {11,111}* (vereinfachst du hier noch weiter?)


Naja, ich glaube man kann \lbrace\underline{1}\rbrace^* bilden.Da ja durch Konkatenation alle Potenzen von 1 gebildet werden können nur eben nicht 1^1

mfg tom

[etikette]

hey leute,

Für a) habe ich folgende Lösung:
({0}{10}*{1}) u {eps} = {01}+ u {eps} = {01}*

Sollte auch passen wenn man sich die Entwicklung der Angabe ansieht:
{01} u {eps}
{0101} u {eps}
{010101} u {eps}
.....

[snax]

hmmm

zu b) glaub das kann man so verstehen {a_} {} u {}*
{a_} {} = {} ... weil irgendwas verkettet mit einer leeren menge ist immer die leere menge
dann bleibt {} u {}* und soweitich glaub/weiß heißts auch irgendwas vereinigt mit einer leeren menge ist wieder eine leere menge

das stimmt so glaube ich nicht

zu c) is glaub ich gleiches prinzip wie oben {}* {a_} {}
{a_} {} = {}, dann bleibt {}* {} = {}, also
{}* {a_} {} = {}

wenn man aber {a}+ mit {eps} verkettet kommt {a}*... das mit {} verkettet wird {}

Bei der Konkatenation ist ja Assoziativität erlaubt ... nur wie wird das in dem Fall angewandt? Ist es egal ob ich zuerst ab oder bc konkateniere? kommen schließlich je nachdem verschiedene Ergebnisse. Vielleicht stimmt auch beides.

[oskar]

1.1a:
({0}{10}*{1})U{eps}
({010}*{1})U{eps}
{0101}+U{eps}
{0101}*
Was meint ihr ?

1.1b:
{a}{}U{}*
{}U{}*
{}*

1.1c:
{}*{a}+{}
{a}+{}
{}

1.1d:
({11}U{111})*
{11,111}*
???

1.1e:
{00}*U({0}{00}*)
{00}*U{000}*
{00,000}*

1.1f:
{a}*n{a,b}+
{a}+

[W.E.]

Hier meine Lösungen hoffentlich liege ich nicht völlig daneben... die stimmen mit deinen eh fast überein aber so eine Notation wie du sie benutzt hab ich bei den Lösungen der Vorjahre nie gesehen... heißt aber nicht das es falsch ist.

a) ({0}{10}*{1}) u {eps} = ({10}{10}*) u {eps} = {10}+ u {eps} = {10}* (da bin ich seeehr unsicher ist auch etwas aus der Luft gegriffen)

b) {a}{} u {}* = {}u{eps} = {eps}

c) {}*{a}+{} = {eps}{a}+{} = {a}*{} = {} (hier verstehe ich deine Vorgehensweise nicht ganz...)

d) ({11} u {111})* = {11,111}* (vereinfachst du hier noch weiter?)

e) {00}* u ({0}{00}*) = {00}* u {0}* = {0}*

f) {a}* n {a,b}+ = {a}+

a,b,c und f habe ich auch so wie du.

d) habe ich {1}*-{1}, da man mit der Angabe ja alle "Mengen" von 1en darstellen kann ausser genau 1.

e) Verstehe ich deshalb nicht, da man mit {0}* ja auch das Leerwort darstellen kann, aber aufgrund von ({0}{00}*) muss ja eine Null vorkommen oder? Der Stern zählt ja nur für die zweiten 0en oder nicht?

[Silent_Bob]

das stimmt so glaube ich nicht


wenn man aber {a}+ mit {eps} verkettet kommt {a}*... das mit {} verkettet wird {}

Bei der Konkatenation ist ja Assoziativität erlaubt ... nur wie wird das in dem Fall angewandt? Ist es egal ob ich zuerst ab oder bc konkateniere? kommen schließlich je nachdem verschiedene Ergebnisse. Vielleicht stimmt auch beides.

\lbrace\underline{a}\rbrace^+ verkettet mit \lbrace\varepsilon\rbrace ergibt wieder \lbrace\underline{a}\rbrace^+
anders bei der Vereinigung da gilt: \lbrace\underline{a}\rbrace^+\cup \lbrace\varepsilon\rbrace = \lbrace\underline{a}\rbrace^*
Bei Assoziativität sind die beiden Ergebnisse immer gleich: (a+b)+c = a+(b+c)



e) Verstehe ich deshalb nicht, da man mit {0}* ja auch das Leerwort darstellen kann, aber aufgrund von ({0}{00}*) muss ja eine Null vorkommen oder? Der Stern zählt ja nur für die zweiten 0en oder nicht?

Ja, der Stern-Operator gilt nur für \lbrace\underline{00}\rbrace
aber der Operator \cup vereinigt die beiden Mengen. dh. in \lbrace\underline{0}\rbrace^* ist \varepsilon enthalten.

[snax]

\lbrace\underline{a}\rbrace^+ verkettet mit \lbrace\varepsilon\rbrace ergibt wieder \lbrace\underline{a}\rbrace^+
anders bei der Vereinigung da gilt: \lbrace\underline{a}\rbrace^+\cup \lbrace\varepsilon\rbrace = \lbrace\underline{a}\rbrace^*
Bei Assoziativität sind die beiden Ergebnisse immer gleich: (a+b)+c = a+(b+c)


Habe nochmal nachgeforscht und wie du richtig sagst ist {eps} verkettet mit {a}+ wieder {a}+ ... trotzdem kommt bei (c) je nach Vorgehensweise entweder {} oder {eps} raus ... wenn man zuerst {eps} mit {a}+ vereinigt kommt also ergebnis die Nullmenge {} und wenn man zuerst {eps} mit {} vereinigt kommt als ergebnis {a}+ wie bei dir. Bin da leider immer noch nicht schlauer ;-(

[Silent_Bob]

Habe nochmal nachgeforscht und wie du richtig sagst ist {eps} verkettet mit {a}+ wieder {a}+ ... trotzdem kommt bei (c) je nach Vorgehensweise entweder {} oder {eps} raus ... wenn man zuerst {eps} mit {a}+ vereinigt kommt also ergebnis die Nullmenge {} und wenn man zuerst {eps} mit {} vereinigt kommt als ergebnis {a}+ wie bei dir. Bin da leider immer noch nicht schlauer ;-(

Vereinigt wird bei Beispiel c nichts, wenn zwischen den Termen kein Operator steht dann ist immer die Konkatenation gemeint, so wie du ja auch auf den Mal-Punkt bei der Multiplikation verzichten kannst.

\lbrace\rbrace^*\lbrace\underline{a}\rbrace^+ \lbrace\rbrace^* \to \lbrace\varepsilon\rbrace\lbrace\rbrace Sternoperator hat die höchste Priorität, so wie du 2^2 + 3 = 4 + 3 und nicht 2^5 rechnest. Die leere Menge funktioniert bei der Konkatenation wie "mal Null".
Laut Folien Seite 18: \lbrace\rbrace A = \lbrace\rbrace bzw. A \lbrace\rbrace = \lbrace\rbrace

[snax]

Mit vereinigt meine ich verkettet also konkatentiert ... habe mich da falsch ausgedrückt ... nichts desto trotz lautet die Angabe {}*{a}+{} also zuerst der Sternoperator er hat die höchste Priorität ... ich verkette {eps} mit {a}+ ... ergibt mir {a}+ {} (MAL 0 wie du richtig sagst) ergibt {}

[Silent_Bob]

Mit vereinigt meine ich verkettet also konkatentiert ... habe mich da falsch ausgedrückt ... nichts desto trotz lautet die Angabe {}*{a}+{} also zuerst der Sternoperator er hat die höchste Priorität ... ich verkette {eps} mit {a}+ ... ergibt mir {a}+ {} (MAL 0 wie du richtig sagst) ergibt {}

Auf dieses Ergebnis komme ich auch. Hab mich im ersten Post verschrieben.

[hagbard85]

Hi!


e.
\lbrace\underline{00}\rbrace^* \cup (\lbrace\underline{0}\rbrace\lbrace\underline{00} \rbrace ^*) = \lbrace\varepsilon,\underline{00},\underline{0000} ,\underline{000000},...\rbrace \cup \lbrace\varepsilon,\underline{0},\underline{000}, \underline{00000},...\rbrace also \lbrace\underline{0}^{2n} \mid n \geq 0\rbrace \cup \lbrace\underline{0}^{2n-1} \mid n \geq 2\rbrace = \lbrace\underline{0}\rbrace^*




Hallo. So wie du es geschrieben hast, kann ich es nachvollziehen, aber ich habe ein grundsätzliches Problem: ist {0 0} (wie es in der Angabe steht) nicht etwas anderes als {00} wie du es beschreibst? Ich komm zwar auf das gleiche Ergebnis, aber nicht auf demselben Weg....


ich hätte es so gelöst:

unter der Annnahme, dass {0 0}* ={0^n}*......

{0 0}* U {0}{0 0}*=
{0^n}* U {0}{0^n}*=
{0^n}* U {0^n}* =
{0^n}* oder {0}* (oder {eps, 0, 0 0, 0 0 0,...}


Was meint ihr?

[manül]

[...] aber ich habe ein grundsätzliches Problem: ist {0 0} (wie es in der Angabe steht) nicht etwas anderes als {00} wie du es beschreibst?

{00} ist für mich eine Menge, die ein Symbol, das aussieht wie zwei Nullen, enthält. Dass die Wörter bei Bob durchgängig Unterstrichen sind, hängt wohl vielmehr von den verwendeten Befehlen in Tex hier im Forum ab :)

[bsoykal]

fur e habe ich so gemeint:

{00}* U ({0}{00}*)=

{eps,00,0000,...}U{0,000,00000,...}=

{0}*

??? BIN ICH FALSCH ???:coolsmile::coolsmile:

[KatzeImSack]

fur e habe ich so gemeint:

{00}* U ({0}{00}*)=

{eps,00,0000,...}U{0,000,00000,...}=

{0}*

??? BIN ICH FALSCH ???:coolsmile::coolsmile:

nö, hab ich auch so.
wenn man zwei "mengenkreise" pinselt und die dann vereinigt sieht mans imho am schönsten dass das so stimmen sollte...

grüße!

[Guybrush333]

also mit kommt bei a) nicht {10}* raus, sondern {01}*

{10}* = {eps,10, 1010, 101010,...}
wenn man an diese jetzt vorne die nullen hängt und hinten die 1en (reihenfolge ist wichtig!) sieht das so aus:
{01, 0101, 010101, 01010101, ...} --> {01}+

wenn man das jetzt mit {}* (eps) vereinigt --> {01}*


irgendwelche einwände? wenn das jetzt nicht stimmt verzweifle ich >_>

lg

[gonzo69]

wie kommt man eigentlich bei f) {a_}* n {a_,b_}+ = {a_}+ ?
steh grad voll auf der leitung :wein:

[Guybrush333]

wie kommt man eigentlich bei f) {a_}* n {a_,b_}+ = {a_}+ ?
steh grad voll auf der leitung :wein:


schreib dir doch einfach die ersten paar "wörter" jeder menge auf, dann sieht man das sehr gut:

{a}* == {eps, a, aa, aaa, aaaa, ...}
{a,b}+ == {a, b, aa, ab, bb, aaa, aab, ...}

in {a,b}+ gibt es also sicher alle wörter die es auch in {a}* gibt mit außnahme von epsilon. beim durchführen der schnittmenge von {a}* und {a,b}+ bleibt also nur:

{a}+

[BananaJoe]

da sind meine lösungen:

a) {01}*
b) {E}
c) { }
d) {1^n | n >= 2 , E)
e) {0}*
f) {a}+

[cherrybonbon]

Naja, ich glaube man kann \lbrace\underline{1}\rbrace^* bilden.Da ja durch Konkatenation alle Potenzen von 1 gebildet werden können nur eben nicht 1^1

die konkatenation ist ja nicht zwingend (oder?). imo gilt 1^1 \in \lbrace1\rbrace*

d) ( \lbrace11\rbrace U \lbrace111\rbrace)* = \lbrace11,111\rbrace* = \lbrace\epsilon,11,111,1111,..\rbrace = \lbrace\epsilon,1^n | 2 <= n\rbrace

[Guybrush333]

die konkatenation ist ja nicht zwingend (oder?). imo gilt 1^1 \in \lbrace1\rbrace*

d) ( \lbrace11\rbrace U \lbrace111\rbrace)* = \lbrace11,111\rbrace* = \lbrace\epsilon,11,111,1111,..\rbrace = \lbrace\epsilon,1^n | 2 <= n\rbrace


wie erzeugst du bitte 1111?

[KatzeImSack]

wie erzeugst du bitte 1111?

ich denke bei {11,111}* einfach die 11 zwei mal durchlaufen?
oder war was anderes gemeint?

[Guybrush333]

ah....

ja klar...

sry ^^

[Phistomefel]

Hallo,

ich hätte bei d {11}+{1}* raus. Damit sollte man doch auch alle 1^n (n>=2) bilden können, oder hab ich da einen Denkfehler drin?

[manül]

ich hätte bei d {11}+{1}* raus.

Da fehlt dir \eps und das + ist auch unnötig.
Kannst aber {11}{1}*u{\eps} machen.

[Al Kupone]

warum am ende ein {\eps}? spielt das eig. keine rolle?

[manül]

warum am ende ein {\eps}? spielt das eig. keine rolle?
Weil du sonst kein \eps im neuen regulären Ausdruck mehr hast und er somit nicht mehr mit der Angabe identisch ist? ;)

[Al Kupone]

was ist mit dem ergebnis {1}* - {1}? eps wäre erhalten u alle potenzen von 1 könnten gebildet werden, mit der ausnahme von 1 natürlich. oder ist das falsch?

[manül]

was ist mit dem ergebnis {1}* - {1}? eps wäre erhalten u alle potenzen von 1 könnten gebildet werden, mit der ausnahme von 1 natürlich. oder ist das falsch?

Das ist keine reguläre Darstellung :p (kam auch in der Übung heute so vor)
Sonst wärs aber wohl korrekt.

[Al Kupone]

ich lasse es lieber bei meiner lösung.. korrekt ist es ja u ist die übung ist dafür da, um auch mal fehler zu machen :shinner:
thanks trotzdem.

[Wauki]

d) ( \lbrace11\rbrace U \lbrace111\rbrace)* = \lbrace11,111\rbrace* = \lbrace\epsilon,11,111,1111,..\rbrace = \lbrace\epsilon,1^n | 2 <= n\rbrace


Seid ihr euch sicher dass das so stimmt?
man kann doch aus der angabe z.B. nicht {11111} bilden, oder irre ich mich da?

denke es geht doch nur :
{eps, 11,111,1111,111111,11111111,111111111,...}
also kein 11111, kein 1111111,... ?

[Clyde]

Seid ihr euch sicher dass das so stimmt?
man kann doch aus der angabe z.B. nicht {11111} bilden, oder irre ich mich da?

denke es geht doch nur :
{eps, 11,111,1111,111111,11111111,111111111,...}
also kein 11111, kein 1111111,... ?

Stimmt sicher so, wieso solltest du es nicht bilden können?

Vereinfacht ergibt die Formel aus d) {11, 111}* - wenn du 11 und 111 verknüpfst kriegst du 11111 ;)

[rgta]

Meine Lösungen:

a) {01}*
(wurde schon genug erklärt)

b) {eps}
({}* = {eps}))

c) {}
(trivial ;)

d) {11, 111}*

e) {0}*
({00}* ist die sprache aller geraden wörter mit dem alphabet {0} und der zweite teil is die sprache aller ungeraden. ergo ergibt sich bei vereinigung die menge aller wörter mit dem alphabet {0})

f) {a}+
(eh kloa)

[Ultrazauberer]

1.1a:
({0}{10}*{1})U{eps}
({010}*{1})U{eps}
{0101}+U{eps}
{0101}*
Was meint ihr ?

1.1b:
{a}{}U{}*
{}U{}*
{}*

1.1c:
{}*{a}+{}
{a}+{}
{}

1.1d:
({11}U{111})*
{11,111}*
???

1.1e:
{00}*U({0}{00}*)
{00}*U{000}*
{00,000}*

1.1f:
{a}*n{a,b}+
{a}+

Hab ich bis auf ein paar Fehler auch so, aber dank dir bin ich aufn Lösungsansatz gekommen, danke, gleich so übersichtlich den ganzen Lösungsweg mitzuposten

[oskar]

Hab die Fehler nun auch gefunden....:)

[Clyde]

Hab ich bis auf ein paar Fehler auch so, aber dank dir bin ich aufn Lösungsansatz gekommen, danke, gleich so übersichtlich den ganzen Lösungsweg mitzuposten

a) ist trotzdem falsch und ergibt {01}*, nicht {0101}* ;)