Automaten Konstruktion
-
Ich soll also einen Automaten erstellen, der 0^n 1^m erkennt. Aber genau das geht doch nicht weil unendlich große Zustandsanzahl, oder?
-
schleifen?
-
Mein Versuch für 0^n 1^n.
-
vip@r schrieb:
Mein Versuch für 0^n 1^n.
http://imageshack.us/photo/my-images/806/29383151.jpg/lol
Dein Automat ist eine Münze.Außerdem war 0^n 1^m gemeint.
Vielleicht so.
q0: 0->q0 1:q1 //bisher nur nullen gelesen
q1: 0->qe 1:q1 //auch einsen gelesen
qe: 0->qe 1:qe //fehler
q0 und q1 akzeptieren. Start bei q0.Bisher war bei Deinen Beispielen schön mlglich, den Zuständen einen Beschreibungstext zu geben, der klar macht, was der Zustand bedeutet. Vielleicht versuchst Du das auch mal.
Und laß pro Pfeil nur ein Zeichen zu und pro Zustand nur zwei ausgehende Pfeile.
Falls mal zufällig zwei Pfeile die selben Start- und Zielknoten haben, kannste immernoch prof-mäßig zusammenfassen. Oder es erstmal lassen.
-
vip@r schrieb:
Mein Versuch für 0^n 1^n.
Nein. Ich habe mich jetzt zwar nicht komplett reingedacht. Aber auf den ersten Blick und keine weiteren -> Der Automat akzeptiert Wörter, die er nicht akzeptieren sollte.
Du solltest dir beim Konstruieren von Automaten nicht nur darüber Gedanken machen, dass die richtigen Wörter akzeptiert werden, sondern auch darüber, dass die "falschen" Wörter nicht akzeptiert werden.
Volkards Denkanstoß hat eigentlich schon ziemlich viel gesagt... Wenn er etwas mit 5 Zuständen meint, dann kann es gut sein, dass du es mit zweien nicht schaffst...
-
vip@r schrieb:
Ich soll also einen Automaten erstellen, der 0^n 1^m erkennt. Aber genau das geht doch nicht weil unendlich große Zustandsanzahl, oder?
Steht das so im Skript? Nee. Da steht mit dieser Argumentation, daß 0^n 1^n nicht geht.
-
-
Nochmal ein Versuch: http://imageshack.us/photo/my-images/38/44887530.jpg/
-
vip@r schrieb:
Nochmal ein Versuch: http://imageshack.us/photo/my-images/38/44887530.jpg/
Der spring bei jedem beliebigen Zeichen und beim nächsten Zeichen wieder nach rechts und immer hin und her.
Er landet bei einer geraden Anzahl von gelesenen Zeichen auf dem rechten Zustand.(rechts ist, wo der Daum,en links ist. Evtl steht das Bild auf dem Kopf)
-
ja eben und das soll er doch oder?
-
hm, irgendwie hab ich momentan überhaupt nicht das gefühl, das ich was verstehe. vielleicht hat jemand lust und vor allem auch zeit ein paar (einfache) sprachen zu posten zu denen ich dann den automat zeichen. sollte doch auch umgekehrt funktioniere, oder?
-
Ich glaub ich hab schon das Problem, dass ich gar nicht wirklich weiß wie ich bei einem gegebenen Automatengraphen weiß, wie man da ein gegebenes Wort wie z.B. 0011 durchgeht. Kann mir das jemand erklären?
-
Hey Leute!
Ich hab mir nochmal Gedanken zu obiger Aufgabe gemacht.
Das letzte Bild das ich gepostet habe war ja eigentlich ein Automat der die Sprache L = {w aus Σ*Bool | |w| mod 2 = 0} erkennt. Das heißt ich hätte ja jetzt quasi schon einen Automat der gerade Wortlänge erkennt.
Und jetzt bräuchte ich eben noch einen Automaten der die Sprache L = {w aus Σ*Bool | 1* 0*} erkennt. Aber so einen gibt's wieder nicht, oder?
Falls doch, könnte man ja jetzt einen Produktautomaten aus beiden Sprachen bauen und wäre fertig, oder?
-
vip@r schrieb:
Und jetzt bräuchte ich eben noch einen Automaten der die Sprache L = {w aus Σ*Bool | 1* 0*} erkennt. Aber so einen gibt's wieder nicht, oder?
Doch, um 18:50.
vip@r schrieb:
Falls doch, könnte man ja jetzt einen Produktautomaten aus beiden Sprachen bauen und wäre fertig, oder?
Das sagt mir gar nichts. Ich muß da wohl krank gewesen sein. Wie macht man aus den beiden einen Produktautomaten?
-
volkard schrieb:
vip@r schrieb:
Falls doch, könnte man ja jetzt einen Produktautomaten aus beiden Sprachen bauen und wäre fertig, oder?
Das sagt mir gar nichts. Ich muß da wohl krank gewesen sein. Wie macht man aus den beiden einen Produktautomaten?
Wenn ich raten müsste, würde ich auf die Kreuzprodukt-Konstruktion für den Automaten der Schnittmenge tippen.
