Aufgabe 1
Gegeben ist ein Transitionssystem TS1, welches aus unendlich vielen Zuständen und den Transitionen {a,b} besteht.Jeder Zustand ist ein Endzustand. "So" ist der einzige Startzustand.
die akzeptierte Sprache L(TS1)= a*|(ba*)* ,oder?
Wäre "So" KEIN ENDZUSTAND, dann wäre L(TS1')=a*b(a*b)* ,oder?
Ergänzung….Jeder Zustand hat eine Schleife über "a" und die Übergänge zwischen Zuständen führen über "b".
Aufgabe 1
Gegeben ist ein Transitionssystem TS1, welches aus unendlich vielen Zuständen und den Transitionen {a,b} besteht.Jeder Zustand ist ein Endzustand. "So" ist der einzige Startzustand.
die akzeptierte Sprache L(TS1)= a*|(ba*)* ,oder?
Nein, warum die | - Alternative ? In deinem regulären Ausdruck kommt z.B. nicht das Wort aba vor, was aber auch akzeptiert wird.
(a*(b))* ist der reg. Ausdruck für die akzeptierte Sprache. Kürzer: (a+b)*
Wäre "So" KEIN ENDZUSTAND, dann wäre L(TS1')=a*b(a*b)* ,oder?
Ja.
(a*(b))* ist der reg. Ausdruck für die akzeptierte Sprache. Kürzer: (a+b)*
Die sind nicht äquivalent, mindestens einer von beiden stimmt also nicht.
(a*(b))* ist der reg. Ausdruck für die akzeptierte Sprache. Kürzer: (a+b)*
Die sind nicht äquivalent, mindestens einer von beiden stimmt also nicht.
Jap stimmt, es muss letzterer sein.
Wenn (a+b)* richtig ist, wie willst du denn "aba" darin unterbringen?
* - es kommt kein einziges Mal oder unendlich oft vor
+ - mindestens einmal
Kann man sich diesen Stern nicht wie eine Potenz vorstellen,ohne dass man die kombinierten Elemente a la 2ab bei *=2 mit berücksichtigt.
Wenn (a+b)* auch aba enthält, dann verstehe ich die Schreibweise nicht. Kann mich jemand aufklären.
+ - mindestens einmal
Das wäre ein hochgestelltes +. Das normale steht für "oder".
Das wäre ein hochgestelltes +. Das normale steht für "oder".
So habe ich es auch gemeint. Ich wusste nur nicht, wie ich hier ^+ hinkriegen soll.
Wenn das normale "+" für oder steht, dann könnte man's auch als (a|b)* schreiben???
@rothose
Ich verstehe nach wie vor nicht, wieso (a+b)* resp. (a|b)* den Ausdruck "aba" enthalten sollten……
Wenn (a+b)* richtig ist, wie willst du denn "aba" darin unterbringen?
(a+b)* => (a+b)(a+b)(a+b) => aba
Das Sternchen kommt sozusagen zuerst.
@Fred
leuchtet jetzt ein.
Wie würde dann der Automat aussehen, der a*|(ba*)* akzeptiert????
(a*(b))*
(a+b)*
Die sind nicht äquivalent
Wären folgende äquivalent?
((a*)b)*
((a+b)*)b | epsilon
Ich verstehe jetzt, wieso ich die Aufgabe in der Klausur nicht lösen konnte. Eine ähnliche Aufgabe hatte es in der Übung gegegebn, die war aber deutlich einfacher gewesen.
Ich sehe, keiner kann hier die RegEx oder Automaten dazu aus den Ärmeln schütteln.
Es muss irgendwelche Verfahren geben, mit hilfe derer die Ausdrücke bei Äquivalenz ineinander überführt werden können. Hoffentlich wird Prof Jantzen hier reinschauen und uns auf die Sprünge helfen.
Soweit ich weiß gibt es einen Verfahren zum bestimmen des eindeutigen minimalen Automaten.
Man könnte also zu zwei regulären Ausdrücken leicht den Automaten aufzeichnen, und beide Automaten minimieren. Sind die minimierten Äquivalent(bis auf Bezeichnung der Zustände), so dürften die ursprünglichen regulären Ausdrücke auch äquivalent sein.
Weiß nur leider aus dem Stegreif nicht mehr wie das Verfahren zum minimieren funktioniert :P
Das Sternchen kommt sozusagen zuerst.
Die Prioritäten für RegEx-Operatoren:
1.Hüllenbildung (*)
2.Verkettung (ab)
3.Oder/Vereinigung (a|b) resp. (a+b)
Ich habe hier:
JFLAP ein Java-Programm(jar) gefunden, welches RegEx in epsilon-NFAs überführt. Damit kann man sich für 2 unterschiedlich formulierte Ausdrücke die entsprechenden NFAs ausgeben lassen.Dann kann man eher feststellen, ob die Ausdrücke äquivalent sind. Die Visualisierungsengine des Programms ist nicht die tollste.
Und
hier ist noch einiges zum Überführungsalgo (RegEx–>NFA). Laut diesem Algo würde der Automat zu (a+b)* ein wenig anders aussehen, als der aus der Klausur, müsste aber zwangslaüfig äquivalent sein, weil sonst könnte er nicht die gleiche Sprache akzeptieren.
…und zwar
Es gibt einen Startzustand So (zugleich Endzustand). Von hier aus gelangt man über a zu So' und über b zu So''. Von So' oder So'' gelangt man jeweils über epsilon zu S1. Hier fängt das Spiel von vorne an……..Das müsste doch ein äquivalenter Automat zu dem aus der Klausur sein, oder?
Ich habe hier: JFLAP ein Java-Programm(jar) gefunden, welches RegEx in epsilon-NFAs überführt. Damit kann man sich für 2 unterschiedlich formulierte Ausdrücke die entsprechenden NFAs ausgeben lassen.Dann kann man eher feststellen, ob die Ausdrücke äquivalent sind. Die Visualisierungsengine des Programms ist nicht die tollste.
Oh, Vorsicht! Ein Programm, das NFAs erzeugt, kann nicht zum Äquivalenztest von regulären
Ausdrücken verwendet werden. Das geht nur dann, wenn das Programm garantiert: "Wenn die
Ausdrücke äquivalent sind, dann sind die Automaten isomorph". Es kann nämlich sein, dass das
Programm zu äquivalenten Ausdrücken verschiedene Automaten liefert.
Ja daher musst beide Automaten minimieren. Denn der minimierte Automat muss eindeutig sein.
Das geht nur dann, wenn das Programm garantiert: "Wenn die
Ausdrücke äquivalent sind, dann sind die Automaten isomorph".
Davon bin ich ausgegangen.
Und wo findet man jetzt das Gedächtnisprotokoll?
Auf der Fachschaftsseite habe ich auch nichts gefunden..
Aufgabe 9 im Gprot:
2. Ist [latex]t_1 \underline{\leftrightarrow} t_2[/latex] entscheidbar?
3. Ist [latex]\neg (t_1 \underline{\leftrightarrow} t_2)[/latex] entscheidbar?
also rein intuitiv sage ich zu beiden "ja" … aber gibt es da eine tolle Begründung / Beweisführung die ich kennen sollte?
Was wäre die Omega-Sprache in 1.4 ????
