Theoretische Informatik reguläre Ausdrücke?
Könnte mir vielleicht jemand helfen. Ich komme bei einer Aufgabe gar nicht klar.
4) Schreiben Sie reguläre Ausdrücke für folgende Sprachen über dem Alphabet Σ = {a,b,c}.
a) Die Menge aller Wörter über Σ, die nicht mit c starten.
b) Die Menge aller Wörter über Σ, die höchstens ein b besitzen.
c) Die Menge aller Wörter über Σ, die mit einem anderen Zeichen enden als sie starten. Beispielsweise befinden sich babc in der Sprache, während sich bacb nicht in der Sprache befindet. Hinweis: Die Wörter haben mindestens die Länge 2.
Danke für die Hilfe
1 Antwort
Du weißt, was reguläre Ausdrücke sind?
Das sind Ausdrücke, die Sprache beschreiben mit folgender Form:
' ' steht für Konkatination. "a b" heißt "b folgt auf a"
'|' steht für Alternative. "a | b" heißt "entweder a oder b".
Dabei bindet ' ' stärker als '|'. "a b | c" heißt also "entweder b folgt auf a, oder c".
Mit Klammern kannst du diese Priorität verändern. "a (b | c)" heißt also "entweder b oder c, folgen auf a".
Ein Beispiel:
Du möchtest die Sprache beschreiben, die die Wörter "gehen" und "stehen" enthält. Ein Regulärer Ausdruck dafür sähe folgendermaßen aus:
('g' | 's' 't') 'e' 'h' 'e' 'n';
Soweit ersteinmal. Jetzt gehen wir aber einen Schritt weiter und erlauben noch wietere Zeichen:
'?' steht für optional. "a?" heißt "entweder a oder nichts".
'+' steht für mehrmals. "a+" heißt "a oder zweimal a oder dreimal a oder .... x mal a".
'*' steht für beliebig oft. "a*" heißt "nichts oder a oder zweimal a oder... x mal a".
Damit lassen sich nun auch kompliziertere Sprachen beschreiben.
Beispiele:
Eine Sprache, die nur aus as besteht und auch das leere Wort akzeptiert:
'a'*;
Eine Sprache, die die Wörter "Kaffee" und "Kaffe" akzeptiert:
'K' 'a' 'f' 'f' 'e' 'e'?;
Eine Sprache, die alle Binärzahlen ohne führende Nullen und die Null akzeptiert:
('0' | '1' ('0 | '1)*);
Wäre dann bei aufgabe a) “(ab)*(c)“ oder (a+b)*a(a+b+c)*b(a+b+c)*c(a+b+c) richtig?
und bei aufgabe b) (a+b+c)*c(a+b+c)*a(a+b+c)*b(a+b+c)
und c komme ich wirklich nicht weiter.