Zu der folgenden Beschreibung soll man einen rationalen Ausdruck bilden:

Die Menge der Zeichenreihen über dem Alphabet {a,b,c}, die mindestens ein a und mindestens ein b enthalten.

Ich komm da zu nichts vernünftiges (alles viel, viel zu lang!).
Ich kann daraus nur einen endlichen Automaten formen, wie geht man da ran?

ich glaub das wäre der korrekte rationale Ausdruck:

(c*b(a+b+c)*ac*)+(c*a(a+b+c)*bc*)

Ich bin aber auch nicht so gut beim bilden von rationalen Ausdrücken…
(Sieht auch lang aus)

Meine Methode: erst einen endlichen Automaten bilden und dann ablesen.

Kann jemand bestätigen ob der rat. Ausdruck korrekt ist?

Wo ist denn das Problem?
Ein rationaler Ausdruck kann doch beliebig lang sein. Solange deine Lösung richtig ist, ist doch egal wie lang sie ist.

Mir ist auf Anhieb auch nur eine lange Lösung eingefallen.

(c*b(a+b+c)*ac*)+(c*a(a+b+c)*bc*)

sieht nicht so richtig aus, da 'aba' nicht drin ist

ganz einfach wäre ja für A=(a+b+c)*

-> AbAaA + AaAbA = A (bAa + aAb) A


obs noch kürzer geht, hmm ;)

z.B. c* (b(b+c)*a + a(a+c)*b) A

Die Menge der Zeichenreihen über dem Alphabet {a,b,c}, die mindestens ein a und mindestens ein b enthalten.

Ich würde den gedanklich einfachsten Weg vorschlagen:

"irgendwas" a "irgendwas" b"irgendwas" oder
"irgendwas" b "irgendwas" a "irgendwas", denn beide Symbole müssen vorkommen.

Als rationaler Ausdruck wird das dann zu

[img]http://mokrates.de/cgi-bin/texstring?%24(a%2Bb%2Bc)%5E*a(a%2Bb%2Bc)%5E*b(a%2Bb%2Bc)%5E*%20%2B%20(a%2Bb%2Bc)%5E*b(a%2Bb%2Bc)%5E*a(a%2Bb%2Bc)%5E*%24[/img]

Was auch nicht kurz ist, aber man sieht sofort das das richtig ist!

(/edit: sah gerade erst Slaters Lösung, die mit der Abkürzung A=(a+b+c)^* schöner aussieht!)

oha [img]http://www.fb18.de/gfx/8.gif[/img] ,
da hab ich mich ja blamiert - naja vor der F-Klausur - viel lernen, wenig Schlaf… [img]http://www.fb18.de/gfx/19.gif[/img]
Am besten nicht darauf hören, was ich da so von mir gebe [img]http://www.fb18.de/gfx/28.gif[/img]

(c*b(a+b+c)*ac*)+(c*a(a+b+c)*bc*)

-> AbAaA + AaAbA = A (bAa + aAb) A


obs noch kürzer geht, hmm ;)

z.B. c* (b(b+c)*a + a(a+c)*b) A

A(ac*b+bc*a)A
spart noch 2 Zeichen [img]http://www.fb18.de/gfx/28.gif[/img]
Irgendwie erinnert mich das an die BucketSort-Implementierung…[img]http://www.fb18.de/gfx/22.gif[/img]