Regular Expression < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Das Alphabet sei {a,b}. Erstelle einen (möglichst einfachen) regulären Ausdruck, der genau jene Wörter matcht, in denen keine zwei aufeinanderfolgende Buchstaben gleich sind.
Beispiele:
gematcht: (leere Eingabe), a, baba, ababa
nicht gematcht: aa, abaa, bbbab, babbab |
Irgendwie find ich keinen geeignete Ansatz zu diesem Beispiel, bin nämlich auch erst am Anfang des Studiums und bin da noch nicht wirklich eingeschossen. Danke schon im Voraus für die Hilfe!
lg Thomas
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo tommy987!
> Das Alphabet sei {a,b}. Erstelle einen (möglichst
> einfachen) regulären Ausdruck, der genau jene Wörter
> matcht, in denen keine zwei aufeinanderfolgende Buchstaben
> gleich sind.
>
> Beispiele:
> gematcht: (leere Eingabe), a, baba, ababa
> nicht gematcht: aa, abaa, bbbab, babbab
> Irgendwie find ich keinen geeignete Ansatz zu diesem
> Beispiel, bin nämlich auch erst am Anfang des Studiums und
> bin da noch nicht wirklich eingeschossen. Danke schon im
> Voraus für die Hilfe!
So ganz spontan, wie wär's mit: [mm] $(ab)^{\star}a^+|(ba)^{\star}b^+$?
[/mm]
Wobei der Stern eine beliebige Widerholung (oder auch gar kein Vorkommen) und das Plus einmal oder keinmal darstellen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:24 Mi 10.01.2007 | | Autor: | tommy987 |
Hallo Bastiane!
> So ganz spontan, wie wär's mit:
> [mm](ab)^{\star}a^+|(ba)^{\star}b^+[/mm]?
> Wobei der Stern eine beliebige Widerholung (oder auch gar
> kein Vorkommen) und das Plus einmal oder keinmal
> darstellen.
Aber das Plus bedeutet ja eigentlich, dass der vorherige Ausdruck min. einmal vorkommen muss, weil dann würde der Ausdruck eine leere Eingabe nicht matchen, oder?
lg Tommy
lg
|
|
|
| |
|
Hallo tommy987!
> > So ganz spontan, wie wär's mit:
> > [mm](ab)^{\star}a^+|(ba)^{\star}b^+[/mm]?
> > Wobei der Stern eine beliebige Widerholung (oder auch
> gar
> > kein Vorkommen) und das Plus einmal oder keinmal
> > darstellen.
>
> Aber das Plus bedeutet ja eigentlich, dass der vorherige
> Ausdruck min. einmal vorkommen muss, weil dann würde der
> Ausdruck eine leere Eingabe nicht matchen, oder?
Wieso, bei der leeren Eingaben kommen doch auch nicht zwei die gleichen Buchstaben hintereinander vor? Ansonsten schreibst du halt [mm] $ab(ab)^{\star}a^+|ba(ba)^{\star}b^+
[/mm]
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:00 Mi 10.01.2007 | | Autor: | tommy987 |
Achja, hab scho gsehn!! Habs etwas falsch interpretiert. Dankeschön!!
lg
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:18 Di 23.01.2007 | | Autor: | tommy987 |
Habs grad nochmals durchgetestet und das kann garnet matchen!! Es steht am Ende a+ oder b+ und das würde heißen, dass es unendliche viele a oder b matched, oder?
lg
|
|
|
| |
|
Hallo,
um es kurz zu machen:
die angegebenen Loesungen stimmten nicht, eine korrekte ist zB
a(ba)^* + a(ba)^*b + a+b+ b(ab)^* + b(ab)^*a
Gruss,
Mathias
|
|
|
| |
|
Liebe Bastiane,
ich hab's als Mitteilung an den anderen Artikel gehängt.
LG
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:43 Mi 24.01.2007 | | Autor: | mathiash |
Hallo liebe Bastiane,
sei nicht traurig, das möcht ich wirklich nicht.
Ok, das einzige, was mir an dieser Lösung nicht gefällt, ist die Tatsache, dass zwar der Term mit der von Dir gegebenen Interpretation richtig ist, jedoch bei regulären Ausdrücken das a^+ stets die Sprache [mm] \{a,aa,aaa, aaaa,\ldots \} [/mm] definiert.
Hättest Du anstelle von a^+ geschrieben: [mm] (a+\lambda) [/mm] bzw [mm] (a+\epsilon) [/mm] für all diejenigen, die den leeren String mit [mm] \epsilon [/mm] bezeichnen, so wäre es richtig gewesen.
Lieben Gruss,
Mathias
|
|
|
|
![[wein]](/images/smileys/wein.gif "[wein]"){kind=small}
