regulärer Ausdruck < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:24 Mo 02.01.2012 | | Autor: | oby |
| Aufgabe | Geben Sie reguläre Ausdrücke für die folgende Sprachen an:
a) Alle Ziffernfolgen im Dezimalsystem, in denen keine Ziffer mehrfach vorkommt.
b) Alle Ziffernfolgen im Dezimalsystem, in denen höchstens eine Ziffer mehrfach vorkommt.
c) Alle Binärzahlen, die nicht den Teilstring 011 enthalten. |
Hallo Matheraum,
Erstmal schönes neues Jahr an alle ;)
Ich komme hier mal wieder nicht weiter und brauche dringend eure Hilfe.
Was wir in der Vorlesung besprochen haben, gibt es die folgenden Operatoren, die ich benutzen kann:
"|" für die Vereinigung
"*" für die Kleensche Hülle
"?" für 0 oder 1 Mal
"+" für 1 oder mehrere Male
"{n}" für n-Mal
also als Beispiel: alle Wörter aus Kleinbuchstaben, die die 5 Vokale in ihrer alphabetischen Reihenfolge enthalten:
K* a K* e K* i K* o K* u K*, wobei K=Menge der Konsonanten.
Oder (0|1)* alle Binärwörter..
Hm, die Beispiele sind mir klar, nur wie geht das Ganze hier? Hab mir lediglich überlegt, dass der * Operator im regulären Ausdruck nicht vorkommen kann, da ja Wiederholungen ausgeschlossen werden. Man könnte alle 10!+9!+8!+... Möglichkeiten einzeln aufschreiben, aber dazu habe ich keine Lust ;)
Vielen Dank schon mal,
Oby
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:04 Di 03.01.2012 | | Autor: | felixf |
Moin!
> Geben Sie reguläre Ausdrücke für die folgende Sprachen
> an:
>
> a) Alle Ziffernfolgen im Dezimalsystem, in denen keine
> Ziffer mehrfach vorkommt.
> b) Alle Ziffernfolgen im Dezimalsystem, in denen
> höchstens eine Ziffer mehrfach vorkommt.
> c) Alle Binärzahlen, die nicht den Teilstring 011
> enthalten.
> Hallo Matheraum,
> Erstmal schönes neues Jahr an alle ;)
> Ich komme hier mal wieder nicht weiter und brauche
> dringend eure Hilfe.
>
> Was wir in der Vorlesung besprochen haben, gibt es die
> folgenden Operatoren, die ich benutzen kann:
> "|" für die Vereinigung
> "*" für die Kleensche Hülle
> "?" für 0 oder 1 Mal
> "+" für 1 oder mehrere Male
> "{n}" für n-Mal
>
> also als Beispiel: alle Wörter aus Kleinbuchstaben, die
> die 5 Vokale in ihrer alphabetischen Reihenfolge
> enthalten:
> K* a K* e K* i K* o K* u K*, wobei K=Menge der
> Konsonanten.
Dann kommt aber jeder Vokal nur genau einmal vor. Falls sie mehr als einmal vorkommen duerfen, aber es jeweils ein Vorkommen geben muss so dass diese "ausgezeichneten" Vorkommen aufsteigend sind, muss man das etwas anders schreiben (K ersetzen durch die Menge aller Kleinbuchstaben).
> Oder (0|1)* alle Binärwörter..
>
> Hm, die Beispiele sind mir klar, nur wie geht das Ganze
> hier? Hab mir lediglich überlegt, dass der * Operator im
> regulären Ausdruck nicht vorkommen kann, da ja
> Wiederholungen ausgeschlossen werden. Man könnte alle
> 10!+9!+8!+... Möglichkeiten einzeln aufschreiben, aber
> dazu habe ich keine Lust ;)
Ich wuerde die Aufgabe so interpretieren wie du. In dem Fall ist es eine endliche Sprache, und ich sehe ebenfalls keine bessere Moeglichkeit als (zumindest bei Zahlen mit allen 10 Ziffern) alle Kombinationen aufzuschreiben.
Aber moeglicherweise ist auch gemeint, dass nicht zwei benachbarte Ziffern gleich sein sollen. (Waer allerdings ungluecklich formuliert...) Passt aber nicht wirklich mit b) zusammen...
Bei b) hat man wieder ein aehnliches Problem...
Teil c) dagegen macht mehr Sinn  Ueberlege dir folgendes: falls mehr als eine 1 am Stueck auftaucht, so muss der Block aufeinanderfolgender Einsen ganz am Anfang stehen. Damit faengt dein Ausdruck mit 1* an, und danach kommt etwas was fuer sorgt dass vor und nach jeder 1 eine 0 steht (oder das Wort zuende ist).
Das solltest du hinbekommen...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:41 Di 03.01.2012 | | Autor: | oby |
Hallo Felix,
Vielen Dank. Ok, also dann sind die beiden ersten Aufgaben wohl zu schwammig formuliert, so dass ich mir weiteres rumgrübeln sparen kann ;)
zur c) hab ich mir nun folgendes überlegt:
[mm] (\varepsilon|0|01|1|10|1^\* (01|0)^\*)
[/mm]
Ich hab also die "lästigen" Fälle für Wörter mit Länge<3 einfach im vorderen Teil in die Oder-Anweisung "reingepresst". Wenn man ein Wort der Länge mindestens 3 erhalten will, so kommt nun deine vorgeschlagene [mm] 1^\*. [/mm] Der letzte Teil sorgt dann dafür (deinem Tipp folgend) dass wenn eine 1 vorkommt, das nur in Kombination mit einer 0 vorkommt.
Würdest du diese Antwort gelten lassen? Ich denke dass meine hierdurch generierten Wörter die gefragten Kriterien erfüllen, aber wie kann ich wissen, ob das dadurch auch alle möglichen solche Wörter generiert werden können? Gibt es da so eine Art Test?
LG, Oby
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:45 Di 03.01.2012 | | Autor: | oby |
Hallo Felix nochmal,
wo wir gerade dabei sind, gibt es auch eine Methode, wie du auf den Tipp mit deiner 1* am Anfang gekommen bist. Oder hast du das einfach gesehen? Ich glaube nicht, dass ich das ohne deinen Tipp hinbekommen hätte :(
LG Oby
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:21 Mi 04.01.2012 | | Autor: | felixf |
Moin Oby,
> wo wir gerade dabei sind, gibt es auch eine Methode, wie
> du auf den Tipp mit deiner 1* am Anfang gekommen bist. Oder
> hast du das einfach gesehen? Ich glaube nicht, dass ich das
> ohne deinen Tipp hinbekommen hätte :(
ich weiss nicht, im Allgemeinen gibt es da keinen guten Trick. Ein Verfahren, welches immer funktioniert, ist sich erst einen endlichen Automaten basteln (das geht recht einfach), und diesen dann in einen regulaeren Ausdruck umzuwandeln. Das geht rein algorithmisch ohne viel Nachzudenken; das Ergebnis ist jedoch meist nicht sehr huebsch...
Ich hab selber erstmal ueberlegt, wie ich das mit einem Automaten machen wuerde, bis mir die Idee kam zu schauen, wieviele Einsen eigentlich hintereinander kommen koennen. Da fiel mir auf, dass nur am Wortanfang mehr als zwei Einsen hintereinander stehen koennen, andernfalls kommt davor irgendwann eine 0 und man hat 011.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:18 Mi 04.01.2012 | | Autor: | felixf |
Moin Oby,
> Vielen Dank. Ok, also dann sind die beiden ersten Aufgaben
> wohl zu schwammig formuliert, so dass ich mir weiteres
> rumgrübeln sparen kann ;)
> zur c) hab ich mir nun folgendes überlegt:
> [mm](\varepsilon|0|01|1|10|1^\* (01|0)^\*)[/mm]
>
> Ich hab also die "lästigen" Fälle für Wörter mit
> Länge<3 einfach im vorderen Teil in die Oder-Anweisung
> "reingepresst". Wenn man ein Wort der Länge mindestens 3
> erhalten will, so kommt nun deine vorgeschlagene [mm]1^\*.[/mm]
wobei 1 (ebenso wie 11 und 00) bereits vom letzten Fall mit abgedeckt ist.
> Der
> letzte Teil sorgt dann dafür (deinem Tipp folgend) dass
> wenn eine 1 vorkommt, das nur in Kombination mit einer 0
> vorkommt.
Hoert sich gut an.
> Würdest du diese Antwort gelten lassen? Ich denke dass
> meine hierdurch generierten Wörter die gefragten Kriterien
> erfüllen, aber wie kann ich wissen, ob das dadurch auch
> alle möglichen solche Wörter generiert werden können?
> Gibt es da so eine Art Test?
Du kannst es formal beweisen Etwa indem du ein beliebiges (aber fest gewaehltes) solche Wort dir vorgibst und zeigst, dass es von der Form ist.
Alternativ kannst du den Umweg ueber endliche Automaten gehen, da ist es teilweise einfacher zu sehen welche Woerter akzeptiert werden und welche nicht.
LG Felix
|
|
|
|
