Beispiel 1.4

[Silent_Bob]

Meine Lösung für 1.4

\Sigma = \lbrace\underline{a},\underline{b},\underline{c} \rbrace und \mathcal L =\lbrace\underline{a},\underline{b},\underline{c} \rbrace - \lbrace\underline{a}^n\underline{b}^n\underline{c} ^n\mid n \geq 0\rbrace mit \mathcal L_1 = \lbrace\underline{a}^i\underline{b}^j\underline{c} ^k \geq 0 und i \ne j\rbrace , \mathcal L_2 = \lbrace\underline{a}^i\underline{b}^j\underline{c} ^k \geq 0 und j \ne k\rbrace,

a) \mathcal L_3 = \lbrace\underline{a}^i\underline{b}^j\underline{c} ^k \geq 0 und i \ne k\rbrace,

somit sind in \mathcal L = \mathcal L_1 \cup\mathcal L_2\cup\mathcal L_3
nur Wörter die sich in allen Koeffizienten unterscheiden.

b) Das Komplement von \mathcal L ist \mathcal \bar L = \lbrace\underline{a}^n\underline{b}^n\underline{c} ^n\mid n \geq 0\rbrace welche nur Wörter mit identischen Koeffizienten enthält.

mfg tom

[gonzo69]

hab das gleiche ... is mir nur zu einfach vorgekommen, darum hab ichs noch nicht gepostet :)

[W.E.]

Hmm, versteh ich nicht:

Was ist wenn ich habe:

L1={a,bb,c} (i ungleich j)
L2={a,b,cc} (j ungleich k)
L3={aa,b,c} (i ungleich k)

jeweils in der Reihenfolge mit den Koeffizienten i,j,k

Da könnte ich doch das Wort abc wenn n=1 darstellen, was aber nicht erlaubt ist? Versteh ich das prinzipiell falsch?

[Silent_Bob]

Hmm, versteh ich nicht:

Was ist wenn ich habe:

L1={a,bb,c} (i ungleich j)
L2={a,b,cc} (j ungleich k)
L3={aa,b,c} (i ungleich k)

jeweils in der Reihenfolge mit den Koeffizienten i,j,k

Da könnte ich doch das Wort abc wenn n=1 darstellen, was aber nicht erlaubt ist? Versteh ich das prinzipiell falsch?

\mathit abc kann mit \mathcal L nicht dargestellt werden, da \mathit abc ja das selbe ist wie \mathit a^{n}b^{n}c^{n} mit n=1
Nicht enthalten in \mathcal L sind alle Wörter bei denen abc mit den gleichen Koeffizienten vorkommen.

mfg tom

[DanyToss]

Ich wage zu behaupten, dass L3 gleich der leeren Menge sein kann, bzw keine Rolle spielt, da doch L1 u L2 bereits ganz L aufspannen können und dabei sicher nicht abc und Poteznen davon erreichen.

(Hab L1, L2 und L mit n= 0 und n= 1 komplett aufgeschrieben und komm so den Schluss)

[gonzo69]

hmmm, klingt irgendwie vernünftig ... hat noch wer eine theorie?

[manül]

Die leere Menge für L3 klingt logisch. Weil durch i!=j (L1) und j!=k (L2) eh schon alles abgedeckt ist.

[Bianconeri]

Kann sein, dass ich völlig daneben lieg aber mit L3 Leere Menge oder L3 mit i ungleich k kann man doch Ausdrücke wie cbaa oder bbbcca nicht bild, was aber definitiv erlaubt ist.

[matthiasb]

Kann sein, dass ich völlig daneben lieg aber mit L3 Leere Menge oder L3 mit i ungleich k kann man doch Ausdrücke wie cbaa oder bbbcca nicht bild, was aber definitiv erlaubt ist.
Kann sein, dass du dich da verlesen hast.
In der Angabe steht L=L_1\cup L_2 \cup L_3, also dass alle regulären Mengen vereinigt L ergeben sollen und nicht
L=L_1\cap L_2 \cap L_3, also dass jede reguläre Menge mindestens alle Anforderungen erfüllen muss.

Hab mir das Beispiel angesehen bevor ich diesen Thread gefunden habe und war zu dem Zeitpunkt noch der Meinung dass die Antwort zu a) auch eine leere Menge sein dürfte.

Gedankenweg: Alles was sichergestellt werden muss ist dass der Fall i= j=k nicht eintritt. Das heißt wir müssen sicherstellen, dass sich immer zwei Werte gleichen dürfen. Und die bereits am Zettel stehenden Restriktionen i\not= j und j\not= k decken das bereits ab.

Graphik zur Veranschaulichung: (0 bedeutet "nicht möglich" 1 bedeutet "zulässig" aber nicht "gegeben")
\begin{tabular}{c|c|c|c} &i=j&j=k&k=i\\\hline i\not= j&0&1&1\\\hline j\not= k&1&0&1\\\hline\\\hline k\not= i&1&1&0\end{tabular}
Wenn ich da meine Tabelle richtig deute bedeutet das für uns, dass die ersten beiden Zeilen bereits jeder Spalte die Möglichkeit geben mit der anderen Variable ident zu sein ohne dass alle drei den gleichen Wert annehmen können.

Die dritte Menge wäre also nur optional.

[etikette]

Kann sein, dass du dich da verlesen hast.
In der Angabe steht L=L_1\cup L_2 \cup L_3, also dass alle regulären Mengen vereinigt L ergeben sollen und nicht
L=L_1\cap L_2 \cap L_3, also dass jede reguläre Menge mindestens alle Anforderungen erfüllen muss.


Ändert meiner Meinung nach nichts an der tatsache dass man nur mit L1 u L2 Wörter wie ca, ba, cb nicht abbilden kann, was mit L alleine durchaus möglich ist.

Mein Vorschlag für L3 deshalb: {ci bj ak | i!=j} u {ci bj ak | j!=k} (allerdings noch nicht ganz durchgedacht)

[matthiasb]

Ändert meiner Meinung nach nichts an der tatsache dass man nur mit L1 u L2 Wörter wie ca, ba, cb nicht abbilden kann, was mit L alleine durchaus möglich ist.Oh, das hab ich komplett übersehen dass die Konkatenation nicht recht kommutativ ist.

Insofern wären dann cba, cab, bac, bca und acb auch alles gültige Wörter?

[manül]

Insofern wären dann cba, cab, bac, bca und acb auch alles gültige Wörter?
scheint so. wird wohl ein langer term...

[david.mihola]

scheint so. wird wohl ein langer term...

Aber sind nicht caba, babacab und aaabacaba auch gültige Wörter? Die liegen doch auch alle in \lbrace \underline{a},\underline{b},\underline{c} \rbrace^\ast, oder?

Ich fürchte also, mit dieser Darstellungsform \lbrace \underline{a}^i,\underline{b}^j,\underline{c}^k \rbrace kommen wir überhaupt nicht weiter. Egal, welche Bedingungen für i, j und k gelten; und selbst dann, wenn wir alle anderen Permutationen von a, b, c aufzählen (vgl. Posting von matthiasb). Denn die drei Wörter, die ich ich oben genannt hab, liegen doch in keiner dieser Mengen (in diesen gibt es jeweils nur einen Block „a“s, einen Block „b“s und einen Block „c“s, während sie sich in L allerdings auch „mischen“ können).

Mal ein anderer Ansatz: Alle Wörter, die mit b oder c beginnen, sind auf jeden Fall gültig, ebenso alle, die mit a oder b enden...

Also: \lbrace \underline{b}, \underline{c} \rbrace \lbrace \underline{a},\underline{b},\underline{c} \rbrace^\ast \cup\lbrace \underline{a},\underline{b},\underline{c} \rbrace^\ast \lbrace \underline{a}, \underline{b} \rbrace

Das würde dann zumindest meine drei Wörter von oben mit einschließen. Aber trotzdem gibt's dann noch Wörter, die mit a beginnen und mit c enden und weder zu L1 noch zu L2 gehören und trotzdem gültig sind (z. B. ababc). Wie man die darstellen kann, ist mir noch unklar... oder bin ich da jetzt völlig auf dem Holzweg?

LG, David

[kodiacc]

Aber sind nicht caba, babacab und aaabacaba auch gültige Wörter? Die liegen doch auch alle in \lbrace \underline{a},\underline{b},\underline{c} \rbrace^\ast, oder?

Ich fürchte also, mit dieser Darstellungsform \lbrace \underline{a}^i,\underline{b}^j,\underline{c}^k \rbrace kommen wir überhaupt nicht weiter. Egal, welche Bedingungen für i, j und k gelten; und selbst dann, wenn wir alle anderen Permutationen von a, b, c aufzählen (vgl. Posting von matthiasb). Denn die drei Wörter, die ich ich oben genannt hab, liegen doch in keiner dieser Mengen (in diesen gibt es jeweils nur einen Block „a“s, einen Block „b“s und einen Block „c“s, während sie sich in L allerdings auch „mischen“ können).

Mal ein anderer Ansatz: Alle Wörter, die mit b oder c beginnen, sind auf jeden Fall gültig, ebenso alle, die mit a oder b enden...

Also: \lbrace \underline{b}, \underline{c} \rbrace \lbrace \underline{a},\underline{b},\underline{c} \rbrace^\ast \cup\lbrace \underline{a},\underline{b},\underline{c} \rbrace^\ast \lbrace \underline{a}, \underline{b} \rbrace

Das würde dann zumindest meine drei Wörter von oben mit einschließen. Aber trotzdem gibt's dann noch Wörter, die mit a beginnen und mit c enden und weder zu L1 noch zu L2 gehören und trotzdem gültig sind (z. B. ababc). Wie man die darstellen kann, ist mir noch unklar... oder bin ich da jetzt völlig auf dem Holzweg?

LG, David

Du hast vollkommen recht. Ist mir auch grad aufgefallen.
Was wohl jedem Poster in diesem Thread nicht auffällt ist das

L_1 = \lbrace \underline{a},\underline{b},\underline{c}\rbrace* \ \neq \ L_2 = \lbrace \underline{a}\underline{b}\underline{c} \rbrace*

ist. d.h. mit L_1 kann man auch wörter wie bcaccab erzeugen. mit L_2 jedoch nur aaabbbbbbcc zB

Also ich hab auch keine Ahnung wie man L3 wählen sollte.. is wohl doch schwieriger die Aufgabe. Das Komplement sollte aber jedoch korrekt sein denke ich?

[Gerros]

Ich hät mir momentan sowas ähnliches gedacht: (\lbrace a \rbrace * \lbrace b \rbrace * \lbrace c \rbrace *)^n mit n>=2
oder \lbrace(a^i b^j c^k)^n\rbrace mit n>=2 und i,j,k >=0
...ich hoff ihr könnt ungefähr nachvollziehen, was mein Hintergedanke ist

[Lukas.P]

Mein lösungsansatz:

L_{1} und L_{2} decken alle wörter mit der Form a^i b^j c^k ab die aber nicht die form a^n b^n c^n haben

d.h.

L_{3} müsste einfach nur noch den rest abdecken also:

L_{3}=\lbrace a,b,c \rbrace * - \lbrace a^i b^j c^k| i,j,k \geq 0 \rbrace

hoffe mal das passt

[david.mihola]

Mein lösungsansatz:

L_{1} und L_{2} decken alle wörter mit der Form a^i b^j c^k ab die aber nicht die form a^n b^n c^n haben

d.h.

L_{3} müsste einfach nur noch den rest abdecken also:

L_{3}=\lbrace a,b,c \rbrace * - \lbrace a^i b^j c^k| i,j,k \geq 0 \rbrace

hoffe mal das passt

Das ist natürlich auch eine Möglichkeit; das heißt dann:

Wir nehmen zuerst von den \lbrace a,b,c \rbrace * alle Wörter der Form a^ib^jc^k weg und geben anschließen jene wieder dazu, wo nicht gilt i = j = k, also wo zumindest ein Exponent anders ist als die anderen beiden.

Klingt gut - ich bin da wohl auf der Leitung gestanden, weil ich geglaubt hab, wir sollen L3 komplett „additiv“ darstellen und nicht eine „subtraktive“ Darstellung (L) durch eine andere ersetzen... oder gibt's doch noch andere Vorschläge, bin selbst bisher sonst auf keinen grünen Zweig gekommen...

LG, David

[Bianconeri]

Du hast vollkommen recht. Ist mir auch grad aufgefallen.
Was wohl jedem Poster in diesem Thread nicht auffällt ist das

L_1 = \lbrace \underline{a},\underline{b},\underline{c}\rbrace* \ \neq \ L_2 = \lbrace \underline{a}\underline{b}\underline{c} \rbrace*

ist. d.h. mit L_1 kann man auch wörter wie bcaccab erzeugen. mit L_2 jedoch nur aaabbbbbbcc zB

aaabbbbbbcc kann man mit diesem L2 nicht bilden. Damit gehen nur Wörter der Form abcabcabc.....

Mein Lösungsvorschlag wäre: Zensiert ^^

Edit: Verdammt stimmt doch nicht aba ist z.b. nicht möglich. OK die Lösung von david.mihola dürfte stimmen. Verdammt gute Idee eigentlich auf den - Operator wäre ich nie gekommen.

[kodiacc]

aaabbbbbbcc kann man mit diesem L2 nicht bilden. Damit gehen nur Wörter der Form abcabcabc.....


hast natürlich recht. aber mein gedanke war klar.. ich meinte nur das man bei L1 die reihenfolge ändern kann.

Das L3 mit dem Komplement erscheint logisch, ja.

[Markus1201]

Ich würde gerne meinen Lösungsvorschlag für eine Diskussion freigeben:

\lbrace \underline{a} , \underline{b} , \underline{c} \rbrace * \lbrace \underline{a} \underline{c} , \underline{b} \underline{a} , \underline{c} \underline{a} , \underline{c} \underline{b} \rbrace \lbrace \underline{a} , \underline{b} , \underline{c} \rbrace *

[majinquinkx]

Legende:
a(i) ...... a hoch i
<> ....... ungleich
E ....... ist Element von


L1 = { a(i) . b(j) . c(k) | i<>j }
L2 = { a(i) . b(j) . c(k) | j<>k }

L1 U L2 = {a(i) . b(j) . c(k) | (i=k) <>j }

mit v E L1, w E L2, x E (L1 U L2) und |v| = |w| = |x| = 3
v,w,x sind beliebige Wörter

Macht Venn-Diagramme dann seht ihr es besser.

L = L1 U L2 U L3 -->
L3 = L - (L1 U L2) =
= { {a,b,c}* - {a(n) . b(n) . c(n)} - {a(n) . b(m) . c(n) | n >=0, n<>m}

dh. L3 sind alle beliebigen Wörter v E L die nicht in (L1 U L2) sind und insbesondere jene Wörter, deren Betrag <> 3 und epsilon

[_ui_]

@Markus

idee sehr gut :D

Ich glaub das ist es - zumindest fällt mir nun echt keine kobination mehr ein die man nicht bilden könnte

[majinquinkx]

warum kann ich cab nicht bilden? ist ja in {a,b,c}* enthalten...

alles was mit a beginnt, das 3 stellig ist, wird auf bestimmte weise ausgeschlossen.
alles was mit b beginnt ist zwansweise 2 stellig, da a = epsilon und wird ausgeschlossen --> in L1 oder L2 enthalten
alles was mit c beginnt ist zwangsweise 1 stellig, da a = epsilon und b = epsilon. kann also nur monotone folge von c sein und wird ebenfalls ausgeschlossen.

[Markus1201]

@Markus

idee sehr gut - denk ist der richtige weg aber:

cab kannst du nicht bilden.

Lösung hab ich allerdings noch keine weil das "ab" ist zurecht nicht in der 4er menge enthalten.

Aber immerhin hab ich wieder eine theorie zerstört :devil:

generell: du kannst keine 3er kombination bilden die ein "ab" am ende hat:
bab

aab wär auch eine kombination aber die wiederum ist mit L1 oder L2 bildbar weil es dir form "abc" hat - nur halt c anzahl = 0

Selbes übrigens für das fehlende "bc" --> cbc nicht mehr möglich

Ich glaube du hast irgendetwas missverstanden, ich kann sowohl cab, bab als auch cbc erzeugen.

[Lukas.P]

@Markus

idee sehr gut - denk ist der richtige weg aber:

cab kannst du nicht bilden.

Lösung hab ich allerdings noch keine weil das "ab" ist zurecht nicht in der 4er menge enthalten.

Aber immerhin hab ich wieder eine theorie zerstört :devil:

generell: du kannst keine 3er kombination bilden die ein "ab" am ende hat:
bab

aab wär auch eine kombination aber die wiederum ist mit L1 oder L2 bildbar weil es dir form "abc" hat - nur halt c anzahl = 0

muss dir leider unrecht geben

mit L1 und L2 kannst du alle erlaubten wörter der form a^i b^j c^k bilden (a,b,c,ab,bc,ac ...)

mit \lbrace a,b,c \rbrace * \lbrace ac,ba,ca,cb \rbrace \lbrace a,b,c \rbrace * solltest du eigentlich den rest abdecken können, um auf dein beispiel zurückzukommen:

cab: \lbrace a,b,c \rbrace * --> {eps}
\lbrace ac,ba,ca,cb \rbrace --> {ca}
\lbrace a,b,c \rbrace * --> {b}

wenn man das nun konkateniert {eps}.{ca}.{b} = {cab}

[_ui_]

bin cih drauf gekommen - aber ihr habt ja scheinbar schon geschrieben ;)

idee genial - aufgabe gelöst

[bsoykal]

L= {a,b,c}*-{a^n b^n c^n}

dann;


L= {b^n a^n c^n,
b^n c^n a^n,
a^n c^n b^n,
c^n a^n b^n,
c^n b^n a^n } oder ?


L1 und L2 interessiert uns nicht, weil da {a^i b^j c^k} nicht in L liegt.

=> L1 U L2 = {}
=> L = L3

:sudern:

[_ui_]

Denk ich zu simpel oder ist

b) einfach nur der abgezogene teil aus der angabe?
Also

a(n) b(n) c(n) | n >= 0

?

[matthiasb]

L_{3} müsste einfach nur noch den rest abdecken also:

L_{3}=\lbrace a,b,c \rbrace * - \lbrace a^i b^j c^k| i,j,k \geq 0 \rbrace
hoffe mal das passtDie Idee hatte ich auch anfangs aber damit würdest du ja nur von der Angabe abschreiben.
In der Angabe steht: L=\{\underline{a},\underline{b},\underline{c}\}*-\{\underline{a}^n\underline{b}^n\underline{c}^n | n\geq 0\}
Und genau das wäre dann unser vorgeschlagenes L_{3}.

[Bianconeri]

Die Idee hatte ich auch anfangs aber damit würdest du ja nur von der Angabe abschreiben.
In der Angabe steht: L=\{\underline{a},\underline{b},\underline{c}\}*-\{\underline{a}^n\underline{b}^n\underline{c}^n | n\geq 0\}
Und genau das wäre dann unser vorgeschlagenes L_{3}.

Das ist so nicht richtig. Unser L3 erlaubt die Wörter aus L1 und L2 nicht. Das L in der Angabe hingegen schon.

[matthiasb]

Das ist so nicht richtig. Unser L3 erlaubt die Wörter aus L1 und L2 nicht. Das L in der Angabe hingegen schon.So, jetzt bin ich ausgestiegen.
Warum sollte die Menge L_{3} nicht auch Elemente enthalten dürfen die in der Menge L_{1} oder L_{2} bereits definiert sind?

[majinquinkx]

verdammt gute frage, tatsache ist, dass L3 sogar echte Teilmenge von L1 U L2 sein kann und die Gleichung L = L1 U L2 U L3 immer noch erfüllt.

moment:
L = L1 U L2 U L3
weiters L = {a,b,c}* - {a(n) . b(n) . c(n) | n>=0} --> ohne L1 U L2 muss, aber auf jeden Fall L3 ergeben. Da bei Vereinigung aller Ls --> L rauskommen muss. so muss L3 das sein, was L1 und L2 nicht sein darf und weiters {a(n) . b(n) . c(n) } berücksichtigt.

das ergibt:

L3 = { a(i) . b(j) . c(k) | i=j } U { a(i) . b(j) . c(k) | j=k} = Komplement(L1 geschnitten L2)
siehe auch De Morgan: http://de.wikipedia.org/wiki/De_Morgansche_Gesetze

[bsoykal]

Ich bin auch bei der gleichen Meinung L3 kann L1 und L2 enthalten .

Und komplement von L = Σ*-L

=>

={a,b,c}* - ({a,b,c}*-{a^n b^n c^n}) = {a^n b^n c^n}

[Lukas.P]

Die Idee hatte ich auch anfangs aber damit würdest du ja nur von der Angabe abschreiben.
In der Angabe steht: L=\{\underline{a},\underline{b},\underline{c}\}*-\{\underline{a}^n\underline{b}^n\underline{c}^n | n\geq 0\}
Und genau das wäre dann unser vorgeschlagenes L_{3}.

das ist nicht die angabe sondern nur eine teilmenge davon ( L - L2 - L3) quasi das was noch fehlt um auf L zu kommen

mMn ist das was ich als Lösung geschrieben hab aber kein Regulärer Ausdruck, würd also die Lösung von Markus nehmen

[Bianconeri]

@matthiasb
Nein das hab ich nicht gemeint. Natürlich kann sich das überschneiden ich wollte nur sagen dass die Lösung http://mitaub.sourceforge.net/cgi-bin/mimetex.cgi?L_{3}=\lbrace a,b,c \rbrace * - \lbrace a^i b^j c^k| i,j,k \geq 0 \rbracenicht das gleiche wie die angabe ist. Wobei es natürlich irgendwie stimmt dass es sehr ähnlich ist.

[Guybrush333]

könnte vielleicht jemand das richtige ergebnis nochmal zusammenfassen.
ich verliere in diesem thread mit diversen fehlern, ausbesserungen etc immer den faden...

haben wir überhaupt ein sicheres ergebnis?

wenn ich schon nicht selbst drauf komme will ich wenigstens das bsp verstehen ^^

[bsoykal]

naja, wie lautet die letzte Losung ? :)

[phex]

markus1201 und Lukas.P habens fast richtig.

Meine Frage wo mein Verständnisproblem lag:
Ist die folgende Mengenangabe korrekt? Was stimmt nicht?
{a,b,c}* = {
a
b
c
aaaa
bbbbbbb
cc
abbccc
cccba
cbbbaaa
bbca
cbbaaacbbaa
cbac
abacb
cbbbaaacccccbbb
...
}

[Al Kupone]

so viel ich weiß, stimmt schon, was du geschrieben hast. die dozentin selbst hat mir erklärt, dass bei solchen mengen die ordnung der symbole keine rolle spielt. nur wenn die menge aus konkatenationen besteht ( wie zB.: L = {abc}) dann darf man diese nicht mehr vertauschen.

[Al Kupone]

weiß nicht ob jemand schon drauf gekommen ist, aber bei punkt a) pro länge von w (also wörter mit der länge 2,3,4,etc) nur 2 formen erlaubt sind..also 10,01,101,010,1010,0101...denn alles andere würde die regel verletzen (wie 0110,1100,1110,0110,etc)..oder irre i mich?

[Al Kupone]

hoppla, flasche thread.sorry