Verständnisproblem zum Thema reguläre Ausdrücke/Sprache?
Hallo, ich hätte ein paar Fragen zum Thema reguläre Ausdrücke/Sprachen, denn es fällt mir im Moment sehr schwer dies zu verstehen, bzw manches davon.
Kurz zu mir, ich bin noch Schülerstudent im 2 Semester, ich beschäftige mich zwar sehr mit dem Stoff, aber manchmal bleibt an der ein oder anderen Stelle nicht so viel hängen und deswegen, erhoffe ich mir, dass ihr mir hier helfen könnt.
Am besten erklärt es sich an zwei Beispielen, wozu auch Musterlösungen vorliegen:
Meine Fragen:
- Warum schreibt man {ab, b} was bedeutet dies? Ich meine in z.B e_1 ist ab und b durch ein + getrennt, das + bedeutet ja "oder" ?
- Wie kommt man auf die Lösung von 3.e?
- Habt ihr irgendwelche Tipps, wie man an solche Aufgaben rangehen soll, komme damit nicht so richtig klar, für mich ist dies irgendwie willkürlich.
Vielen Dank im Voraus.
Liebe Grüße
Marc
3 Antworten
Naja, {ab,b} ist die Menge, die die Strings "ab" und "b" als Elemente beinhaltet. Die Aussageform
x ∈ {ab,b} bedeutet daher x = ab oder x = b.
Zu 3e: Eigentlich ist die Lösung durch einen relativ intuitiven Ansatz erreichbar:
Wir überlegen uns zunächst, wie der erste Buchstabe des Wortes lauten kann. Naja, entweder a oder b oder c (oder gar kein Buchstabe, aber den Spezialfall lösen wir später).
Wenn es ein c ist, ist alles ok, aber wenn es ein a oder b ist, ist die Gesamtanzahl der a's und b's zu diesem Zeitpunkt ungerade. Damit das Wort trotzdem in der Sprache enthalten ist, muss später wieder ein a oder ein b kommen. Wir fokussieren das erste a oder b, das wir danach finden und erhalten zunächst den Ausdruck:
(a + b)c*(a + b) + c.
Nachdem wir entweder ein c oder eine Sequenz (a+b)c*(a+b) gelesen haben, fragen wir uns, was der nächste Buchstabe sein kann. Mit derselben Überlegung wird wieder die Sequenz "c" oder "(a+b)c*(a+b)" folgen (oder das leere Wort). Daher folgern wir induktiv, dass jedes Wort der Sprache dem Ausdruck
((a+b)c*(a+b)+c)* genügt. Der letzte Stern löst auch das Problem mit dem leeren Wort.
e1 = ((ab)* + b*) + (e + a)
heißt:
nach einer auch leeren Folge von ab kommt entweder nix oder genau ein a
oder
nach einer auch leeren Folge von b kommt entweder nix oder genau ein a
ababbba geht nicht. Wenn man mit ab anfängt, muss es mit ab weiter gehen und danach darf noch ein a kommen.
Das kann man auch als
ausdrücken, wobei x für ab oder b steht (x ist Element der Menge {ab, b}) und y genau für nix oder b (y ist Element der Menge {lambda, b}
Je nach Literatur steht entweder lambda (für leer) oder epsilon (für empty) für das leere Wort.
Dass lambda für nix steht, habe ich aus dem Zusammenhang geschlossen.
Sorry, kleiner aber feiner Fehler:
e1 = ((ab)* + b*) + (e + a)
Das zweite + ist zuviel. Dieser Ausdruck würde bedeuten, dass eine beliebig lange Folge von ab oder von b gebildet werden muss oder stattdessen ein einzelnes a oder gar nichts. Ohne das zweite + ist es so, wie ich geschrieben habe, also ein einzelnes a wird optional angehängt.
Als Regex in PHP wäre e1 (aus der Aufgabe): ^((ab)*|b*)a?$
Schade, dass an den Unis immer eigene Schreibweisen benutzt werden, so dass man bei bereits anderweitig erworbenem Vorwissen umdenken muss und erneut, wenn man das Gelernte in der Praxis anwenden will.
Wenn du regex Tester googelst, kommst du u.a. bei regex101.com heraus. Da kann man reguläre Ausdrücke (in PHP und anderen Dialekten) ausprobieren.
{ab,b} wäre eine Menge, kein regulärer Ausdruck udn bei Menge trennt man die Objekte nunmal durch Kommata.
Wieso steht lambda für nix?