Erweiterte reguläre Ausdrücke sind reguläre Mengen - Beweis |
01.05.2012, 10:07 | Christian1 | Auf diesen Beitrag antworten » |
Erweiterte reguläre Ausdrücke sind reguläre Mengen - Beweis Guten Morgen liebes Forum! Ich habe hier ein Übungsblatt mit einer Aufgabe,die ich einfach nicht lösen kann. (Im Anhang befinden sich die Teilaufgaben und die dazugehörigen Ausdrücke) Und zwar sind einige erweiterte reguläre Ausdrücke gegeben und ich soll zeigen, dass sie ebenfalls eine reguläre Menge sind. Die andere Teilaufgabe sagt, dass es für jeden erweiterten regulären Ausdruck E noch ein E' mit der gleichen Menge gibt. Ich hoffe, mir kann jemand helfen =) Mit freundlichen Grüßen Christian Meine Ideen: Nun fehlt mir leider auch schon der direkte Ansatz für diese Aufgabe. Dass die regulären Ausdrucke auch jeweils die dazugehörige Menge haben,die in der Aufgabe steht, ist klar. Doch wie kann ich zeigen, dass es so ist? Für 1. z.B. : "leeresWort" ist Element von Epsilon Es gibt eine Menge M1, die eine Teilmenge von Epsilon ist, so dass : "M1 := "leeresWort" (Formeleditor funktioniert bei mir aus irgendeinem Grund nicht)...ist das in irgendeiner Weise ein richtiger Ansatz? Ich versteh diese Aufgabe leider so überhaupt nicht... |
||
05.05.2012, 16:06 | Abakus | Auf diesen Beitrag antworten » |
RE: Erweiterte reguläre Ausdrücke sind reguläre Mengen - Beweis Hallo, was genau ist eine reguläre Menge (Definition?) ? Das müsste hier der Ausgangspunkt sein. Wenn ihr es über Grammatiken definiert habt, ist für die genannten Fälle eben eine Grammatik anzugeben, die alle genannten Worte enthält .. und keine anderen. Dabei lassen sich die gegebenen Voraussetzungen ausnutzen, zB mit S -> AB, A Startvariable für Sprache 1, B für Sprache 2, lässt sich zeigen, dass das Produkt regulär ist. Abakus |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|