Reguläre Ausdrücke "kürzen"

Eser
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 6. Okt 2004 18:20

Reguläre Ausdrücke "kürzen"

Beitrag von Eser »

Hi,

hab mal ne kurze Frage zur Bildung von regulären Ausdrücken.
Ich hab immer ein Problem einen kurzen regulären Ausdruck zu bilden.

Zum Beispiel will ich einen Regulären Ausdruck über dem ALphabet {a,b,c} bilden, der mir ALLE Wörter bildet deren Länge immer durch 3 teilbar ist.

Wörter wären demnach aaa, abcbbb, bcaabcbbc, usw.
Wie würde der reguläre Ausruck dazu aussehen?
Wenn ich es strikt aufteile, dann wäre der längste aber korrekte (und einfachste) reg. Ausdruck folgender:

(aaa)*(aab)*(aac)*(aba)*(aca)*(abc)*(acb)*(acc)*(abb)*, das wäre aber nur der Teil des Ausdrucks mit ALLEN Wörter mit Prefix a, das gleiche wäre für b und c. Aber das ist montrös. Hierbie musste ich nicht lange nachdenken, weil ich ja sofort weiss wie die Wörter aussehen müssen. Aber wie fasse ich das ganze geschickt zusammen?

Man sieht das a IMMER anfängt, somit könnte man den auch vorne schreiben. Und dann?

Benutzeravatar
plane
Computerversteher
Computerversteher
Beiträge: 337
Registriert: 21. Okt 2005 00:18

Beitrag von plane »

(a+b+c)(a+b+c)(a+b+c)((a+b+c)(a+b+c)(a+b+c))*

damit hätteste alle drin, Wörter der Länge 3 und dann 6,9,12...

yagami
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 5. Okt 2006 03:02

Beitrag von yagami »

hi,

ein regulärer ausdruck für deine Sprache wäre :

((a+b+c) (a+b+c) (a+b+c))*

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

also, wenns allein um länge 3 gehen soll, dann weißte das jede "stern operation" 3 zeichen hervorbringt, d.h. du brauchst 3 ausdrücke die sagen welche zeichen das seien können und gleichzeitig festlegen, das es 3 Zeichen seihn MÜSSEN (oder keins, je nachdem ob das leere wort € L sein darf)
also, wenn wir auch das leere Wort akzeptieren würd ich das so machen:
((a | b | c) (a | b | c) (a | b | c))*

wenn das leere Wort nich akzeptiert werden soll würd ich den ersten ausdruck ohne sternoperation angeben, un danach das, was sich wiederholen darf

(a | b | c)(a | b | c)(a | b | c)((a | b | c) (a | b | c) (a | b | c))*

aber mir passierts auch oft das ich zu große Ausdrücke formulier, d.h. evtl gehts kürzer, aber das ergebnis is auf jedenfall ein Reg Expr der zur Sprache passt

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

hm, ich bin zu langsam :S

Eser
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 6. Okt 2004 18:20

Beitrag von Eser »

So ein Mist. Auf sowas muss ich kommen.
Hab nämlich gerade die Klausur vom 6.März 06 gemacht und da wollte man ja einen Ausdruck für Wörter deren Länge modulo 3 gleich 1 ist.

Demnach wäre die Antwort (a+b+c)((a+b+c)(a+b+c)(a+b+c))*
Ich wollte das erstmal nur mit modulo 3 gleich 0 machen.
Das blöde ist nur, in der Klausur dauert das zu lange bis ich auf sowas komme. Naja üben halt. Danke nochmal an alle.

Benutzeravatar
plane
Computerversteher
Computerversteher
Beiträge: 337
Registriert: 21. Okt 2005 00:18

Beitrag von plane »

yagami hat geschrieben:hi,

ein regulärer ausdruck für deine Sprache wäre :

((a+b+c) (a+b+c) (a+b+c))*
Wörter der Länge 0... werden bei dir akzeptiert...werden diese nicht akzeptiert...siehe meine Lösung oben ...

yagami
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 5. Okt 2006 03:02

Beitrag von yagami »

hmm..ich glaub das leer Wort muss auch akzeptiert werden da: 0/3 = 0

Eser
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 6. Okt 2004 18:20

Beitrag von Eser »

Ok, dann nochwas:
Es wurde gefragt ob der Ausdruck (a+b+c)(a*b*c*)* + 0* gerade \(\Sigma^*\) für ein \(\Sigma=\{a,b,c\}\) entspricht.

Ist denn nicht schon (a*b*c*)* das gesamte \(\Sigma^*\)?

Es geht mir darum den regulären Ausdruck zu bilden um JEDES BELIEBIGE Wort über ein \(\Sigma\) bilden zu können und das wäre in dem Fall (a*b*c*)*, oder?
Zuletzt geändert von Eser am 2. Apr 2007 15:27, insgesamt 1-mal geändert.

Benutzeravatar
plane
Computerversteher
Computerversteher
Beiträge: 337
Registriert: 21. Okt 2005 00:18

Beitrag von plane »

ja also ich würde sagen das ganze entspricht sigma* weil das leere wort ist drinne durch leeremenge* wörter der länge 1 sind drin, der länge 2 und der länge x....

Eser
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 6. Okt 2004 18:20

Beitrag von Eser »

Das leere Wort ist ja auch nur in (a*b*c*)* drin, wegen dem * aussen. Und auch alle Wörter beliebiger Länge.

Ich wollte damit nur sagen, das (a+b+c) und das 0* überflüssig sind, denn (a*b*c*)* ist doch schon das \(\Sigma^*\)

Benutzeravatar
plane
Computerversteher
Computerversteher
Beiträge: 337
Registriert: 21. Okt 2005 00:18

Beitrag von plane »

das ganze soll einen ja auch nur verwirren...

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag von marlic »

Eser hat geschrieben:Das leere Wort ist ja auch nur in (a*b*c*)* drin, wegen dem * aussen. Und auch alle Wörter beliebiger Länge.
[/tex]
Naja, durch die Konkatenation mit (a + b + c) ist epsilon ja nicht mehr drin ;)

f_noell: ganz genau!

Antworten

Zurück zu „Archiv“