kennt sich jemand mit endlichen automaten aus?

MoxxiManagarm

MoxxiManagarm

Top Contributor
Heyoka955 hat gesagt.:
Glaube jetzt hab ich das verstanden☺
Zum Vergrößern anklicken....
Dann wird es Zeit für eine Übungsaufgabe um das zu überprüfen :cool:

{ w | w ∈ {a, b}*, sowohl a als auch b dürfen maximal 2 mal hintereinander eintreten } HINT: 5 Zustände
{ w | w ∈ {a, b}*, die Anzahl von a und b darf sich zu keinem Zeitpunkt um mehr als 2 unterscheiden } HINT: 5 Zustände
{ w | w ∈ {a, b}*, w darf nicht mit Doppel-a oder Doppel-b beginnen } HINT: 4 Zustände
 
Zuletzt bearbeitet:
H

Heyoka955

Gast
Also aber man muss am Anfang lange nachdenken.
Ich gehe folgend ran, ich mache Beispiel für die Wörter die fink
MoxxiManagarm hat gesagt.:
Dann wird es Zeit für eine Übungsaufgabe um das zu überprüfen :cool:

{ w | w ∈ {a, b}*, sowohl a als auch b dürfen maximal 2 mal hintereinander eintreten } HINT: 5 Zustände
{ w | w ∈ {a, b}*, die Anzahl von a und b darf sich zu keinem Zeitpunkt um mehr als 2 unterscheiden } HINT: 5 Zustände
{ w | w ∈ {a, b}*, w darf nicht mit Doppel-a oder Doppel-b beginnen } HINT: 4 Zustände
Zum Vergrößern anklicken....
werde ich machen wenn ich Zeit fidne. Aber die ersten beiden sind machbar.
Ich muss nachhause und erstmal Sport und Dann eine Programmier Aufgabe Lösen.
 
H

Heyoka955

Gast
MoxxiManagarm hat gesagt.:
Dann wird es Zeit für eine Übungsaufgabe um das zu überprüfen :cool:

{ w | w ∈ {a, b}*, sowohl a alsauch b dürfen maximal 2 mal hintereinander eintreten } HINT: 5 Zustände
{ w | w ∈ {a, b}*, die Anzahl von a und b darf sich zu keinem Zeitpunkt um mehr als 2 unterscheiden } HINT: 5 Zustände
{ w | w ∈ {a, b}*, w darf nicht mit Doppel-a oder Doppel-b beginnen } HINT: 4 Zustände
Zum Vergrößern anklicken....
Zu a muss man folgendes betrachten,

Wiir dürfen maximal aa oder bb.
Das heißt der erste q muss drei Pfeile haben einmal zu sich selbst also a einmal dann wieder a zum nächsten und dann dritte Pfeil b zum anderen.
Das heißt jedes q hat drei Möglichkeiten mit den Pfeilen.
Also sorry bin unterwegs
 
mihe7

mihe7

Top Contributor
Nachdenken, probieren, verwerfen, nachdenken - das ist der Prozess. Das fällt schwer und mit der Zeit und wachsender Erfahrung wird es natürlich leichter, aber da musst Du durch.
 
H

Heyoka955

Gast
mihe7 hat gesagt.:
Kein Video, eine Begründung von Dir - die Herleitung. Was hast Du gemacht usw.?
Zum Vergrößern anklicken....
Nea ist ja selbstverständlich. aber von Dfa ist also ,am schaut von wo man anfängt nachem das man gemacht hat muss man von der Tabelle die werte für die einzelnen mengen einsetzten und gucken wohin der weg führt und wenn man das gemacht hat dann übernimmt man für den nächsten zustand.
 
H

Heyoka955

Gast
mihe7 hat gesagt.:
Kein Video, eine Begründung von Dir - die Herleitung. Was hast Du gemacht usw.?
Zum Vergrößern anklicken....
bei nea müssen wir achten ob also wir fangen beu q0 an und schauen uns wann wo wir hingehen können falls a erscheint. Wnn dies der fall ist dann schreiben wir all emengen zu dem er hingehen kann, also in dem falle wäre das qo(zu sich selber) und q1 und q2. und dann schauen wir bei b und da gibt es keine kante dazu.
Nachdem wir das gemacht haben, schauen wir uns q1 an und gucken was passiert wenn a kommt und da passiert nix und wenn b eintritt geht er zurück zu q0. Und bei q2 ist das gleiche wie q0 denn er kann zu sich selber und zu q0 und bei kommt kein Ergebnis.
 
mihe7

mihe7

Top Contributor
Dein letzter Kommentar ist schon viel besser als der vorletzte. Du beginnst also beim einzigen Startknoten des NFA und übernimmst ihn in den DFA. Im NFA erreichst Du mit einem a die Zustände q0, q1 und q2. Daher fasst Du diese zu einem neuen Zustand {q0, q1, q2} (kurz: q0q1q2) zusammen und hast im DFA einen Übergang (q0, a, q0q1q2). Für b gibt es von q0 aus keinen Zustandsübergang.

Soweit habe ich Dich verstanden und das ist auch korrekt. Beim Rest ist mir allerdings nicht klar, was Du da betreibst. Da fehlt mir der Zusammenhang zum DFA.
 
H

Heyoka955

Gast
mihe7 hat gesagt.:
Dein letzter Kommentar ist schon viel besser als der vorletzte. Du beginnst also beim einzigen Startknoten des NFA und übernimmst ihn in den DFA. Im NFA erreichst Du mit einem a die Zustände q0, q1 und q2. Daher fasst Du diese zu einem neuen Zustand {q0, q1, q2} (kurz: q0q1q2) zusammen und hast im DFA einen Übergang (q0, a, q0q1q2). Für b gibt es von q0 aus keinen Zustandsübergang.

Soweit habe ich Dich verstanden und das ist auch korrekt. Beim Rest ist mir allerdings nicht klar, was Du da betreibst. Da fehlt mir der Zusammenhang zum DFA.
Zum Vergrößern anklicken....
also bei dfa ist die erste zeile und zweite zeile richtig? oder wie verstehe ich die aussage
 
mihe7

mihe7

Top Contributor
Das kann sein, ich kann das Gekritzel nicht entziffern.

Bis jetzt haben wir nur einen Übergang (eine Kante), nämlich für a von q0 nach q0q1q2.

Code: 
       a
q0 --------> q0q1q2

Wie geht es jetzt weiter? Bei Deiner Erklärung oben fehlt noch was (ich meine, dass es in Deinem Bild vorhanden ist).
 
H

Heyoka955

Gast
dann gibt es nix meiner Meinung nach bei q0 in dfa wir können dann zur q0q1q2 als zustand also so


a b
q0q1q2 für a müssen wir gucken wohin q0 hingeht wenn a kommt
und dann müssen wir gucken wohin q1 hingeht bei a
und dann q2. und diese mengen schreiben wir auf
 
mihe7

mihe7

Top Contributor
Heyoka955 hat gesagt.:
q0q1q2 für a müssen wir gucken wohin q0 hingeht wenn a kommt
und dann müssen wir gucken wohin q1 hingeht bei a
und dann q2. und diese mengen schreiben wir auf
Zum Vergrößern anklicken....
Genau. Du schaust im DFA den nächsten Zustand an, hier also q0q1q2. Dieser beschreibt ja die Zustandsmenge {q0,q1,q2} im NFA. Daher schaust Du Dir im NFA für jeden dieser Zustände die Übergänge für a (und später für b) an.

Im NFA kommst Du von q0 aus mit einem "a" wieder zu {q0, q1, q2}. [EDIT: der Vollständigkeit halber sei erwähnt, dass es keine Kante für a von q1 aus gibt, und für q2 folgen die Zustände {q0,q2}. Insgesamt hat man also {q0, q1, q2}] Im DFA gibt es daher einen Übergang von q0q1q2 nach q0q1q2 für ein a.

Code: 
                    a
                 +----+
                 |    |
       a         v    |
q0 --------> q0q1q2 --+

Wie sieht es bei b aus?
 
H

Heyoka955

Gast
mihe7 hat gesagt.:
Genau. Du schaust im DFA den nächsten Zustand an, hier also q0q1q2. Dieser beschreibt ja die Zustandsmenge {q0,q1,q2} im NFA. Daher schaust Du Dir im NFA für jeden dieser Zustände die Übergänge für a (und später für b) an.

Im NFA kommst Du von q0 aus mit einem "a" wieder zu {q0, q1, q2}. [EDIT: der Vollständigkeit halber sei erwähnt, dass es keine Kante für a von q1 aus gibt, und für q2 folgen die Zustände {q0,q2}. Insgesamt hat man also {q0, q1, q2}] Im DFA gibt es daher einen Übergang von q0q1q2 nach q0q1q2 für ein a.

Code: 
                    a
                 +----+
                 |    |
       a         v    |
q0 --------> q0q1q2 --+

Wie sieht es bei b aus?
Zum Vergrößern anklicken....
wäre dann das {q0}
 
mihe7

mihe7

Top Contributor
Code: 
                    a
                 +----+
                 |    |
       a         v    |
q0 --------> q0q1q2 --+
   <--------
       b
Da es jetzt im DFA keine Zustände gibt, die noch nicht betrachtet wurden, bist Du fertig.
 
H

Heyoka955

Gast
also wie zeichen ich das ? meine Tabelle sieht so aus
 

Anhänge

  • tutu.png
    tutu.png
    927,1 KB · Aufrufe: 129
mihe7

mihe7

Top Contributor
In der linken Spalte hast Du die Startknoten (der Kanten) und in den rechten Spalten die Zielknoten der Kanten für a bzw. b.
 
MoxxiManagarm

MoxxiManagarm

Top Contributor
Heyoka955 hat gesagt.:
wie sollte man bei so einer aufgabe vorgehen
Zum Vergrößern anklicken....
Es gibt eigentlich kein Schema F, aber vielleicht ein paar Tricks, frage mal @MoxxiManagarm ....
Zum Vergrößern anklicken....

Hmpf, meine Tipps habe ich doch schon gegeben :confused: Für solche Aufgaben wir in Aufgabe 1 muss man sich "einfach" nur logisch überlegen was die möglichen Zustände sind, was diese bedeuten und was passiert wenn Event a oder b in diesem Zustand eintritt. q0-n sowie a und b sind mehr oder weniger nur "Platzhalter" für Zustandsbeschreibungen und Aktionen. Du könntest in jeden Kreis auch einen zustandsbeschreibenden Text schreiben und statt a und b das Event benennen.

Überspitzte Darstellung des Küchenbeispiels...
kueche.png

Frage an Heyoka zum Nachdenken: Was würde sich an diesem Diagram ändern wenn man die Prämisse ergänzt man will kein Essen auf dem Tisch vergammeln lassen.

Und das Schema für meine erste Übungsaufgabe von Tobias ist richtig. Mein Graph in der "Musterlösung" ist zwar anders angeordnet würde aber auf das Gleiche hinauslaufen. Ich hatte noch 2 weitere Übungsaufgaben ergänzt, falls du nochmal Langeweile bekommst :p
 
Zuletzt bearbeitet:
H

Heyoka955

Gast
mihe7 hat gesagt.:
Ach @Heyoka955, wir haben doch von Anfang bis zum Schluss den kompletten Graphen konstruiert. Wie um alles in der Welt kommst Du jetzt darauf, dass es plötzlich einen Übergang von q0 zu sich selber geben sollte?
Zum Vergrößern anklicken....
Du hast gesagt dass eine Kante fehlt. Und da q0 zu sich selber geht dachte ich die wäre diese jedoch habe ich geschaut und auch gemerkt macht sich kein Sinn da q0 zu sich selber in dem
Anderen Zustand schon steht.

Also es fehlt nur eine Kante vielleicht würde ich sagen q0q1q2 zu sich selber weil wir in der Tabelle gesehen haben dass von
Dort aus zu sich selber nochmal geht ?
 

Aktuelle Jobs

Neue Themen


Oben