Theoretische Informatik (reguläre Grammatik)?
Ich stehe vor folgender Aufgabe
L1=(a^nb^m | n>=0, m>=1)
L=(a,bab)
1. Erstellen Sie für die Sprache L1 und L2 sowie für die Sprache L3= L1 U L2 jeweils einen endlich Automaten
2. Geben Sie die vollständige Grammatik für L1/L2/L3 an
Ich weiß, was ein DEA ist und wie er aufgebaut ist. Ich weiß ebenfalls, wie eine Grammatik aufgebaut ist
G=( V,T,P,S)
Allerding weiß ich nicht, wie ich nun von diesen Sprachen ein DEA erstellen soll. Ich weiß auch nicht, was hier die Vereinigung verwirkt und wie ich in Aufgabe 2 auf die Gesamte Grammatik (V,T,P,S) kommen soll. Vor allem verstehe ich nicht, wie ich auf P kommen soll.
Ich bräuchte, wenn's geht, eine verständliche Schritt für Schritt Erklärung. Vielen Vielen Dank schon Mal!!
1 Antwort
Ich kann gerade nicht direkt alles liefern, morgen vielleicht mehr.
Erstmal nur soviel: überlege dir jeweils für die Sprache wie die Wörter davon aussehen und dann wieviele verschiedene Zustände du brauchst. Die Vereinigung ist genauso wie bei Mengen, alles was in dem einen oder anderen Sprache ist, ist auch in der Vereinigung.
Die erste Sprache würde ich in zwei Zuständen machen, erst einer der a erzeugt mit Schleife auf sich selbst und dann mit b oder Epsilon in einem akzeptierenden Zustand übergeht der b erzeugt. Alternativ ohne Schleife wären es vier Zustände, davon zwei akzeptierend. Zwei Zustände die hin und her a erzeugen und zwei Zustände die hin und her b erzeugen. Aus den ersten Zuständen führt ein Übergang mit b zu den b Zuständen. So ist gewährleistet, dass stets 0-n a und dann 1-m b als Wörter entstehen. Mit folgender Notation habe ich versucht das deutlich zu machen, Zustände in Klammern sind akzeptierend:
z⁰ --a--> z¹
z⁰ --b--> (z²)
z¹ --a--> z⁰
z¹--b--> (z³)
z² --b--> (z³)
z³ --b--> (z²)
Ich bin nicht sicher ob man Epsilon für a⁰ explizit erzeugen muss. Ergänz es entsprechend wenn nötig
L2 ist etwas schwieriger. Wir brauchen einen Zyklus der nur a erzeugt und akzeptierend ist und einen der bab erzeugt und erst dann akzeptiert. Vielleicht nicht die eleganteste Lösung aber eine Lösung wäre genau das, vom Initial Zustand gehen zwei Pfade ab einmal mit a zu einem zwei Zustände Zyklus die beide akzeptierend sind und hin und her a erzeugen und ein Pfad mit b zu einem bab Zyklus aus 3 Zuständen, wovon der letzte akzeptierend ist. Der letzte kann wieder einer der a Zustände sein, das spart einen Zustand.
z⁰ --a--> (z¹)
z⁰ --b--> z²
z¹ --a--> (z³)
z¹--b--> z²
z³ --a--> (z¹)
z³--b--> z²
z² --a--> z⁴
z⁴--b-->(z¹)
Disclaimer: ich habe schon einige Jahre mich damit nicht mehr beschäftigt und nur eben die Kenntnisse auf die schnelle aufgefrischt. Es kann gut sein, dass ich die Syntax falsch habe oder Dinge vorschlage die nicht zulässig sind. Verlass dich also nicht einfach auf die Richtigkeit meiner Antwort.
So etwas ergänzt. Vielleicht kommt noch mehr wenn ich etwas Ruhe habe das Thema weiter aufzufrischen.
Okay vielen Dank schon Mal ich werde es weiter probieren