3. Konstruktion eines Automaten

Konstruktion eines Automaten

  • V

    Hi Leute!

    Ich hab diese Sprache hier:

    L = {1n 0m | n,m in N Λ (n+m) mod2 = 0}

    Wie kann ich nun einen Automaten konstruieren der mir diese Sprache erkennt? Einfach einen NEA bauen ist hier nicht, weil ich nicht recht weiß wie ich mit 1n un 0m umgehen soll.

    Könnt ihr mir helfen?

    0
  • V

    Mir ist gerade eingefallen, dass ich ja einen modulo 2 Automaten zeichnen kann und einen 1*0* Automat. Die zwei zusammen könnten doch dann den gesamten Automaten ergeben, oder?

    0
  • V

    vip@r schrieb:

    Hi Leute!

    Ich hab diese Sprache hier:

    L = {1n 0m | n,m in N Λ (n+m) mod2 = 0}

    Wie kann ich nun einen Automaten konstruieren der mir diese Sprache erkennt? Einfach einen NEA bauen ist hier nicht, weil ich nicht recht weiß wie ich mit 1n un 0m umgehen soll.

    Könnt ihr mir helfen?

    Entweder zwei Automaten machen, einen, der erst erst 1 annimmt und sobald die erste 0 gefallen ist nur noch 0 und einen, der jedes zweite Zeichen annimmt, und die beiden Automaten kombinieren, ich glaube, man sagt, das Produkt aus zwei Automaten erstellen. Falls Ihr das hattet, sollste vielleicht das üben.

    oder, was ich machen würde: Einfach einen Automaten hinmalen.

    Name       FolgeBei1  FolgeBei0  akzeptiert
Gerade1    Ungerade1  Ungerade0  Jau
Ungerade1  Gerade1    Gerade0    Nöö
Gerade0    Fehler     Ungerade0  Jau
Ungerade0  Fehler     Gerade0    Nöö
Fehler     Fehler     Fehler     natürlich nicht

    (Wäre das Produkt aus Gerade/Ungerade und 1/0/Fehler)

    0
  • V

    Könntest du vielleicht noch ein bisschen weiter darauf eingehen wie du so schnell auf die Liste gekommen bist?

    Und auch noch ein bisschen erklären wie das "einfach Automat hinmalen" geht?

    0
  • V

    vip@r schrieb:

    Könntest du vielleicht noch ein bisschen weiter darauf eingehen wie du so schnell auf die Liste gekommen bist?

    Indem ich mir einen Kugelschreiber genommen habe, ein Kreischen für den Startzustand, ein 1-Pfeilchen zu einem Folgezustand und von da ein 1-Pfeilchen zurück. Dann den Startzustand mit Sonnenstrahlen verziert, was heißen sollte, daß er akzeptiert, dann den Rest gemalt.

    vip@r schrieb:

    Und auch noch ein bisschen erklären wie das "einfach Automat hinmalen" geht?

    Sorry, leider nein. Das plane ich nicht so bewußt mit Worten oder nachvollziehbaren Schritten, sondern es klappt einfach. Und wenn's mal nicht paßt, wird's passend gemacht.
    Das sollte Dir aber auch gelingen, wenn Du ein paar geübt hast.

    0
  • V

    Hm, erstmal Danke für deine Hilfe.

    Ich hab jetzt mal versucht den Automaten aus eigener Gedankenkraft zu zeichnen. Das war ja mal nix so genaus. Da ist mir die zwei Automaten-Methode und Verknüpfung mit den Abschlusseigenschaften lieber.

    Naja Übung macht den Meister.

    Ich hätte hier jetzt nochmal eine Sprache zu der ich einen Automaten malen soll:

    l = {w in Σ*Bool | w enthält 11 genau 2 mal}

    Tip: 111 enthält 11 zweimal.

    Ich hab mir jetzt erstmal einen NEA gezeichnet den ich dann in einen DEA mit Potenzmengenkonstruktion umwandeln will. Hier ist mal ein Link auf meine Zeichnung des NEAs: http://imageshack.us/photo/my-images/710/57179606.jpg/

    Denkst du, dass der so stimmen könnte?

    0
  • V

    vip@r schrieb:

    Denkst du, dass der so stimmen könnte?

    Die Idee ist gut und überzeugend.
    Aber ich hab's nicht so mit NEAs.

    Ich kann nur anbieten, einen DEA zu entwickeln.

    edit: Es geht um
    ~~l = {w in Σ[h]*[/h][t]Bool[/t] | w enthält 11 genau 2 mal}
    (Anmerkung: 111 zählt auch als zweimal 11)
    ~~
    l = {w in Σ*Bool | w enthält 11 mindestens 2 mal}
    (Anmerkung: 111 zählt auch als zweimal 11)

    Name     Bei1     Bei0     azeptiert
m        m1       m

    Soweit klar
    Und dann überlege ich mir immer für den einen neu hinzuerfundenen Kreis, wohin es bei 1 und wohin es bei 0 zu gehen hat. Wichtig ist, daß man weiß, welchen Zustand der jeweilige Kreis denn bedeutet. Mit der soeben erfundenen m-Notation (m steht für Müll) kann ich es sogar als Tabelle entwickeln und muß kein Bildchen malen.

    Name     Bei1     Bei0     azeptiert
m        m1       m
m1       m11      m

    Name     Bei1     Bei0     azeptiert
m        m1       m
m1       m11      m
m11      feddisch m11m

    Name     Bei1     Bei0     azeptiert
m        m1       m
m1       m11      m
m11      feddisch m11m
feddisch feddisch feddisch ja

    Name     Bei1     Bei0     azeptiert
m        m1       m
m1       m11      m
m11      feddisch m11m
feddisch feddisch feddisch ja
m11m     m11m1    m11m

    Name     Bei1     Bei0     azeptiert
m        m1       m
m1       m11      m
m11      feddisch m11m
feddisch feddisch feddisch ja
m11m     m11m1    m11m
m11m1    feddisch m11m

    edit2: FEHLER! Der Automat erkennt mindestens zweimal 11 und nicht genau zweimal 11.

    0
  • V

    vip@r schrieb:

    Ich hab jetzt mal versucht den Automaten aus eigener Gedankenkraft zu zeichnen. Das war ja mal nix so genaus. Da ist mir die zwei Automaten-Methode und Verknüpfung mit den Abschlusseigenschaften lieber.

    Wäre mir zu viel Arbeit bei so kleinen Sachen.

    vip@r schrieb:

    Naja Übung macht den Meister.

    Leider ist das Automatenmalen erstaunlich übungsresistent! Man kann es sofort oder man lernt es nie (so ist es üblich, aber nicht gut). Ist ja auch irgendwie klar, denn man hat ja Nullinger davon, wenn man nicht zum Ergebnis kommt. Entsprechend Nullinger Teil-Lernfortschritt, den man immer Häppchenweise weiter ausbauen könnte.

    Vielleicht liegt Dir meine Schrittweise Entwicklung. Falls ja, falls Du meine obige Entwicklung nachvollziehen kannst, können wir es mit Üben mal pro-bieren. Ich entwickle Dir auf diese Weise so viele kleine DEAs wie Du willst. Und Du schickst mir eine Kopie der Klausur, wo eine rote 1 drunter steht. Und gibst mir eine Kiste Bier aus. Ich denke, das könnte klappen und besonders interessiert mich der Beweis, daß man es lehren und erlernen kann.

    0
  • V

    Diese obige schrittweise Entwicklung hast du jetzt auf welches Beispiel angewendet?

    Auf dieses Beispiel: l = {w in Σ*Bool | w enthält 11 genau 2 mal}

    oder

    dieses Beispiel: L = {1n 0m | n,m in N Λ (n+m) mod2 = 0}

    Zitat: "... kann ich es sogar als Tabelle entwickeln und muß kein Bildchen malen."

    Hm, das bringt mir jetzt nicht so viel die Tabelle, da ich es in der Klausur als Graph malen muss. Aber vielleicht kann man ja die Tabelle in einen Graphen umsetzen? Geht das? Das würde dann bedeuten, ich müsste erst die Tabelle machen und dann aus der Tabelle den Graphen extrahieren.

    Aber wie oben schon geschrieben würde ich gern wissen auf welche Sprache du die ausführliche Entwicklung bezogen hast, damit ich das mal Schrittweise durchspielen kann. Am besten bei einem Beispiel bei dem ich die Lösung schon habe. Danach wäre es sehr nett wenn du mir eine sehr einfache Sprache geben würdest bei der ich dann die Tabelle respektive Graph entwickle und dir dann meine entwickelte Tabelle kurz abtippe damit du sie überprüfen kannst.

    Bist du damit einverstanden?

    Würde mich freuen!

    0
  • V

    vip@r schrieb:

    Diese obige schrittweise Entwicklung hast du jetzt auf welches Beispiel angewendet?

    Auf dieses Beispiel: l = {w in Σ*Bool | w enthält 11 genau 2 mal}

    Ja.
    edit: NEIN! Siehe edit oben. Ich hatte die Aufgabestellung falsch gelesen.

    vip@r schrieb:

    Zitat: "... kann ich es sogar als Tabelle entwickeln und muß kein Bildchen malen."

    Hm, das bringt mir jetzt nicht so viel die Tabelle, da ich es in der Klausur als Graph malen muss. Aber vielleicht kann man ja die Tabelle in einen Graphen umsetzen? Geht das?

    Ja, geht sogar ganz einfach. Jede Zeile ist ein Kreischen und Bei0 und Bei1 ergeben die Pfeilchen auf die anderen Kreischen.

    vip@r schrieb:

    Das würde dann bedeuten, ich müsste erst die Tabelle machen und dann aus der Tabelle den Graphen extrahieren.

    Nein, nichtmal.
    Tabelle war für mich nur einfacher zu posten als das äquivalente Bildchen. Und unfertige Tabelle entspricht genauso dem unfertigen Bildchen. Statt eine neue Zeile in die Tabelle einzufügen, kann man genauso einen neuen Kreis zeichnen und die beiden abgehenden Pfeile.

    vip@r schrieb:

    Aber wie oben schon geschrieben würde ich gern wissen auf welche Sprache du die ausführliche Entwicklung bezogen hast, damit ich das mal Schrittweise durchspielen kann. Am besten bei einem Beispiel bei dem ich die Lösung schon habe.

    Was Du magst. Bestell bei mir eine Entwicklung und ich versuche es.

    vip@r schrieb:

    Danach wäre es sehr nett wenn du mir eine sehr einfache Sprache geben würdest bei der ich dann die Tabelle respektive Graph entwickle und dir dann meine entwickelte Tabelle kurz abtippe damit du sie überprüfen kannst.

    Bist du damit einverstanden?

    Klar. Aber Du hast doch mehr Übungsaufgaben vorrätig als ich, oder?

    Würde mich freuen![/quote]

    0
  • G

    Danke fuer diesen Thread.

    Ich hatte lange keine Automaten mehr konstruiert, habe aber anhand der Aufgabenstellungen hier gesehen, dass ich es wohl noch so halbwegs hinkriege.

    Ich habe mir dabei ueberlegt, was ich eigentlich bei der Konstruktion mache und habe festgestellt, dass ich eigentlich nicht sooo systematisch vorgehe. Aber es scheint aehnlich wie bei der Programmierung zu sein. Man man einen Algorithmus konstruieren will, bei dem man an gewissen Stellen unterschiedliche Faelle unterscheiden muss, dann hat man fast das gleiche Problem:

    Man muss sich ueberlegen, welche Faelle (Zustaende) auftreten koennen und was man in so einem Fall jeweils macht. Wenn man intuitiv programmiert, dann geht man die Funktionsweise des Algorithmus praktisch in seinem Kopf durch. "Wie wuerde ich das mache?!" und schreibt es auch so ins Programm. Bei der Konstruktion von derartigen Automaten, die bestimmte Sprachen akzeptieren sollen, kann man es genauso machen. Man ueberlegt sich im Kopf wie ein gegebenes Wort anfangen kann und abhaengig vom ersten Zeichen geht es dann gleich in unterschiedliche Zustaende. Dann denkt man weiter, was beim naechsten Zeichen passiert. Kommt man mit einem bestimmten Zeichen in einen schon dagewesenen Zustand? Oder stellt ein neues Zeichen eine ganz andere Situation dar?

    0
  • V

    Nochmal ein Versuch mit

    l = {w in Σ*Bool | w enthält 11 genau 2 mal}

    und diesmal lese ich die Aufgabestellung richtig. "genau 2 mal".

    "m" steht wieder für "Müll": Eine beliebig lange Zeichenfolge, die keine 11 drin hat und mit 0 endet, also die bloß Müll ist und keine 1 zum Anbauen liefert.

    name       bei0      bei1     akzeptiert
m          m         m1

    Also ein Kreis mit m drin beschriftet und ein 0-Pfeil auf m und ein 1-Pfeil auf einen neuen Kreis mit m1 beschriftet. Die nächste Aufgabe ist es, zu überlegen, wohin die beiden Pfeile von m1 hingehen werden.

    name       bei0      bei1     akzeptiert
m          m         m1
m1         m         m11

    Also von m1 gehts beim Lesen einer 0 nach m zurück. Beim Lesen einer weiteren 1 aber gehts in einen neuen Zustand namens m11.

    Und dann habe ich mir Kreis für Kreis vorgenommen und immer überlegt, wie der Folgezustand bei 0 und bei 1 wohl heißen müßte.

    Als nächstes den m11 begutachten:

    name       bei0      bei1     akzeptiert
m          m         m1
m1         m         m11
m11        m11m      m111

    Und so weiter. Zeile für Zeile ist jeweils genau die Überlegung, was bei 1 und was bei 0 für ein Zustand folgen müßte.

    name       bei0      bei1     akzeptiert
m          m         m1
m1         m         m11
m11        m11m      m111
m111       m111m     zuviel
zuviel     zuviel    zuviel
m11m       m11m      m11m1
m11m1      m11m      m11m11
m11m11     m11m11m   zuviel
m11m11m    m11m11m   m11m11m1
m11m11m1   m11m11m   zuviel

    Soweit, sogut. Alle Zustände haben zwei Ausgänge.
    Außer m111m, den habe ich noch nicht fertig.
    Hier fällt mir auf, daß "m111m" und "m11m11m" gleichwertig sind.
    Sie möchten zusammenfallen. Ich sollte mir einen besseren Namen dafür einfallen lassen, sagen wir mal "gutm". Entsprechend wollen "m111" und "m11m11" zusammenfallen und "gut" heißen. Das spart bestimmt viele Zustaände/Zeilen/Kreise.
    Eigentlich bin ich ja faul und würde sie gerne jetzt schon zusammenfallenlassen.
    Aber nö, ich mach mal brutal weiter.

    name       bei0      bei1     akzeptiert
m          m         m1
m1         m         m11
m11        m11m      m111
m111       m111m     zuviel
zuviel     zuviel    zuviel
m11m       m11m      m11m1
m11m1      m11m      m11m11
m11m11     m11m11m   zuviel
m11m11m    m11m11m   m11m11m1
m11m11m1   m11m11m   zuviel
m111m      m111m     m111m1
m111m1     m111m     zuviel

    Ihgitt, ist der riesig geworden. Hoffentlich ist er korrekt. Da steigt ja kein Schwein mehr durch. Und der Prof bekommt Augenkrebs, wenn er schauen will, ob der stimmt. Nach meinem Mittagsschläfchen muß ich das nochmal probieren mit "gut" und "gutm".

    Wobei man das Bildchen ja auch (mit genau gleichem Ergebnis) formal optimieren könnte, wenn man mit Bleistift gemalt hätte. Ach, so viel spart die Optimierung wohl doch nicht ein.

    0
  • G

    volkard schrieb:

    Nochmal ein Versuch mit

    l = {w in Σ*Bool | w enthält 11 genau 2 mal}

    Ich habe auch mal mein professionelles Automaten-Malprogramm angeworfen und aufgezeichnet, wie meiner so in etwa aussieht.

    http://img838.imageshack.us/img838/382/automat.png

    Vielleicht ist in dem allerdings auch ein Fehler. Wer weiss. 🙂 Der Startzustand hat links einen Balken, die akzeptierenden Zustaende rechts.

    EDIT:

    @volkard: Mir erscheint Dein Automat korrekt zu funktionieren. ...zumindest wenn die Zustaende akzeptieren, von denen ich ausgehe, dass sie akzeptieren.

    EDIT2: Frage: Muss man bei einem Automaten eigentlich fuer alle Zustaende und alle moeglichen Eingaben Folgezustaende einbauen? Oder kann man einfach sagen, dass die Eingaben, die zu keinem Zustand fuehren, offensichtlich nicht akzeptiert werden?

    0
  • V

    Gut, dann werde ich mal versuchen diese Aufgabe nachzuvollziehen.

    Einige Fragen hab ich aber schon noch:

    -> Was ist "bei0" und "bei1" und was soll dabei das "bei" bedeuten? Edit: Damit ist wahrscheinlich gemeint mit welchem Zeichen (1 oder 0) in welchen neuen Zustand gewechselt wird, oder?
    -> m steht für Müll. Ok. Das m ist aber doch auch der jeweilige Zustand. Ich bin es bis jetzt gewohnt, dass man die Zustände durchnummeriert. Bspw.: q0, q1, q2, ..., qn-1, qn. Was soll hier nun m, m1, m11 und dann so komische aneinanderkettungen m11m11 bedeuten? Edit: Kann es sein, dass hiermit gemeint ist welche Zustand der Zeichenkette in dem jeweiligen Zustand gerade vorzufinden ist?

    -> Was soll zuviel heißen? Geht bspw. vom Zustand m111 mit einer 1 die Transition dann in einen Deadstate?

    -> Wie setze ich nun konkret die Liste in einen Graphen um? Edit: Link von meinem Graphen den ich aus der Liste extrahiert hab: http://imageshack.us/photo/my-images/441/43941107.jpg/ (Startzustand ist mit Pfeil gekennzeichnet)

    Großes Edit: Wie erkenne ich denn nun aus der Liste welche Zustände akzeptierend sind?

    0
  • G

    vip@r schrieb:

    Großes Edit: Wie erkenne ich denn nun aus der Liste welche Zustände akzeptierend sind?

    Naja, volkard hat seine Zustaende praktisch nach den Zeichen benannt, die bisher aufgetaucht sind. Entsprechend sind m111m, m111m1, m11m11, m11m11m und m11m11m1 akzeptierend. Die erfuellen ja die Bedingung, die an die zu akzeptierende Sprache gesetzt sind.

    ...Der von Dir gezeichnete Automat scheint uebrigens ein paar Kanten zu haben, die in volkards Liste nicht auftauchen und die falsch sind. Vor allem die Verbindungen zwischen m11m1 und m111m fallen mir gerade auf.

    0
  • V

    Gut, da hast du Recht.

    Wenn ich nun bspw. Das Wort w=1111 durchlaufen lasse, dann enthält dieses Wort 11 genau zweimal. Aber genau dieses Wort wird vom Automat aber nicht erkannt...; weil die vierte 1 nämlich im DS landet...

    Ich glaub aber, dass ein Fehler in meinem Graphen ist... Oder kann das jemand verifizieren?

    Edit: 1111 enthält 11 dreimal. Shit.

    0
  • V

    Ich hab jetzt mal nochmal versucht aus eigener Gedankenkraft einen Automaten für die Sprache zu erstellen. Tut's dann der einfache nicht auch?

    Link: http://imageshack.us/photo/my-images/857/22923694.jpg/

    Kann das mal jemand noch durchprobieren? Mir wäre kein Wort eingefallen das nicht geht!

    0
  • G

    vip@r schrieb:

    Ich hab jetzt mal nochmal versucht aus eigener Gedankenkraft einen Automaten für die Sprache zu erstellen. Tut's dann der einfache nicht auch?

    Link: http://imageshack.us/photo/my-images/857/22923694.jpg/

    Kann das mal jemand noch durchprobieren? Mir wäre kein Wort eingefallen das nicht geht!

    Was ist mit "1110" und 110110?

    0
  • V

    1110 ist doch an der Stelle bei der dritten 1 schon akzeptiert. Da interessiert doch dann nicht mehr was danach kommt, oder?

    Bei 110110 ist es doch das gleich, oder? was nach der vierten 1 kommt ist doch egal, da der Automat schon akzeptiert hat, oder?

    Ja, oder hab ich hier was grundsätzlich falsch verstanden?

    0
  • G

    vip@r schrieb:

    1110 ist doch an der Stelle bei der dritten 1 schon akzeptiert. Da interessiert doch dann nicht mehr was danach kommt, oder?

    Bei 110110 ist es doch das gleich, oder? was nach der vierten 1 kommt ist doch egal, da der Automat schon akzeptiert hat, oder?

    Ja, oder hab ich hier was grundsätzlich falsch verstanden?

    Es könnten ja auch "1111" oder "110111" kommen. Die dürfen nicht akzeptiert werden. Die vorherigen aber schon.

    0
  • V

    Gregor schrieb:

    EDIT2: Frage: Muss man bei einem Automaten eigentlich fuer alle Zustaende und alle moeglichen Eingaben Folgezustaende einbauen? Oder kann man einfach sagen, dass die Eingaben, die zu keinem Zustand fuehren, offensichtlich nicht akzeptiert werden?

    Klar kann man das so handhaben. Man muß ja nur einen Zustand

    name       bei0      bei1     akzeptiert
hoelle     hoelle    hoelle   nein

    automatisch anlegen und jeden weggelassenen Pfeil per Konvention dahinzeigen lassen.

    Und das macht man auch.

    http://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat sagt
    "Alternativ kann man die Übergangsfunktion als partielle Funktion definieren, sodass nicht von jedem Zustand aus für jedes Eingabesymbol ein Nachfolgezustand existieren muss. Das Eingabewort gilt somit auch dann als verworfen, wenn beim Lesen der Eingabe ein Übergang nicht möglich ist."

    0
Anmelden zum Antworten