Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Probleme bei konstruktion eines DFA
Hey,
bei mir hängts gerade bei einer, ansich, relativ einfachen DFA-Konstruktion.
Folgende reguläre Sprache ist gegegeben:
L={w∈Σ*|Anzahl(a)=Anzahl(b)=n}
Die Anordnung der a’s und b’s ist beliebig, nur müssen jeweils gleich viele a’s und b’s (welches die einzigen Variablen sind) identisch sein. Länge des Wortes ist n.
Nun muss zu dieser Sprache ein Automat konstruiert werden. Für n=1,2,3,… kein Problem, aber sobald das n größer wird, scheitert es bei mir.
Von welchem n soll man denn nun ausgehen, bzw. gibt es da eine komfortable Lösung?
Zur Info, es geht um Klausuraufgabe I-2, Frühjahr 2004.
Danke schonmal für die Hilfe
Stell dir ein (n+1)x(n+1) Gitter vor. Jeder Gitterpunkt ist ein Zustand.
Start ist in der NordWest-Ecke.
Mit a läuft man Südwärts, mit b gen Osten.
Landet man in der SüdOst-Ecke, so acceptiert der Automat, läuft man irgendwo aus dem Gitter raus, landet man in einem (zusätzlichem) nichtacceptierenden und nicht mehr verlassbaren Zustand.
That’s it.
Das ist mir auf jeden Fall klar, aber wie MALE ich das? 
Mir einfach irgendein n (z.b. n=2) rauspicken, oder was wird dort erwartet? Evtl. langt auch nur Dein Text als Antwort?
wenn’s n a’s gibt und n b’s, dann ist die gesamtlaenge 2n
Das mit dem Gitter hilft aber auch nur bei vorgegebenem maximalen n.
Gehts auch mit beliebigem n?
Das ist ja das Problem. n ist vorgegeben als Element aus N.
Und einen Automaten kann ich nur für fixes n zeichnen. Deswegen ist mir nicht ganz klar, was für eine Antwort in dieser Klausuraufgabe erwartet wird.
Wenns nicht fix ist, gibt es keinen Automaten, ich würd da einfach einen Übergang stricheln und die dann Zustände dann von 1,1 bis n,n benennen
Schade, dass es so formal korrekte Herren aus THI nicht hinbekommen, eine Aufgabe eindeutig zu formulieren. Das scheint ja öfter vorzukommen.
Danke für Eure Hilfen, ich dachte schon, wir wären komplett bescheuert, da wir ewig über eine eindeutige Lösung gegrübelt haben.
n ist schon fix denke ich … n ist halt ein beliebiger fester wert aus N.
und da greift halt das gittermodel.
wenns die klausur ist die ich denke dann gibts ja später ein M das ALLE diese verschieden 2n langen wörter zusammenfasst. das wiederum ist ja dann
(a|b)* mit der einschränkung |w(a)| = |w(b)| = n
und da kannste wieder das wort a^n b^n wählen und zerpumpen …
also wenn das diese aufgabe ist macht ja dann der erste teil ohne festes n wenig sinn, da du dir ja sonst den 2ten teil sparen kannst.
wie gesagt … wenns diese aufgabe ist …
Kuck mal hier:
https://uni.unclassified.de/1549,2#15242
Zieh dir den anhang und vergleiche mit L_3,n (Blattmitte)
PS: Bitte dran denken, dass M2 auf demselben Blatt falsch war (die b Pfeile gehen in die andere Richtung).