Theoretische Informatik - Automaten etc.

Megaman2044

Lt. Junior Grade
Registriert
Feb. 2005
Beiträge
365
Hallo,

aufgrund des anstehenden Abiturs in Hessen, versuche ich aktuell den Stoff für Informatik aufzuarbeiten. Darunter gibt es ein Gebiet Theoretische Informatik. Dazu hätte ich mehrere Fragen.

Bevor ich euch frage, wollte ich grundsätzlich fragen, ob solche Fragerei hier erwünscht ist. Vielen Dank im vorraus!

Gruß Marc
 
Ok, super. Ich hab bei folgender Aufgabe ein Problem:

"Gegeben sei die Sprache S, die aus allen Wörtern der Form a^n besteht, wobei n durch 3 oder durch 4 (oder durch beide) teilbar ist. Geben Sie einen zugehörigen DEA an."

Ich hab es versucht komme, aber nicht genau hin. Im Anhang findet ihr ein Automaten. Er akzeptiert "aaa", "aaaa" auch "aaaaaaaa"
 

Anhänge

  • A-Automat.jpg
    A-Automat.jpg
    9,5 KB · Aufrufe: 911
Sollte imho gehen, wenn du den "Zustands-Kreis" auf kgV(3,4) erweiterst und dann alle vielfachen von 3 bzw. 4 zum Endzustand machst.
 
@Narkry: Bei dir dürfte aber auch "aaaaaa" nicht gehen, obwohl es durch 3 teilbar ist!

@derlolomat: Man soll einen Deterministischen Automaten erstellen, hast du nicht einen Nicht-deterministischen erstellt?
 
@derlolomat: das ist ein NEA

@Megaman2044: überleg dir die Reihe, die durch 3 oder 4 teilbar ist.
Also: 3,4,6,8,9,12,15,16,18,20,21,24,27,28,30,32,33,...
Und nun schau dir die Abstände zwischen den Zahlen an
Das wäre: 1,2,2,1,3,3,1,2,2,1,3,3,1,2,2,1,....

Wenn du die Reihe jetzt scharf anschaust, sollte dir ein Muster auffallen. Damit kannst du dir dann den Automaten bauen.
 
Zuletzt bearbeitet:
Kann es sein, dass das eine Trickfrage ist? Ich komm nämlich auch gerade nicht auf die Lösung. -.-
 
@snow1: Man könnte die Reihe sogar mit 3 beginnen lassen, dann hätte man diese "Folge":
3,1,2,2,1,3
also bräuchte man 6 Endzustände...
 
Ja hast recht 1668mib, ich hab´s jetzt auch raus. Ich hab´ die ganze Zeit nach einem Trick gesucht, dabei muss man das nur stupide abarbeiten und dann kommt man irgendwann an deinen Endzustand, den man mit dem Zustand nach dem Startpunkt verbinden kann.

Also merke:
Niemals bei sowas nach einem Trick suchen, sondern einfach ganz blöd lösen, Schritt für Schritt.

@snow: Also ich wusste, dass das die Anzahl der Schritte bis zu einem Endzustand ist, allerdings dachte ich, dass es mit viel weniger Endzuständen funktioniert und hab´ deswegen, wie gesagt, nach einem "Trick" gesucht. So´n Müll. -.-

Ein Grund mehr das Heftchen zu hassen:
Bla
 
Zuletzt bearbeitet:
Zeichne dir mal einen Automaten mit 12 Zuständen (q0 bis q11) und verbinde die sequentuell. Dann als Endzustände q0, q3, q4, q6, q8, q9. q11 verbindest du dann noch mit q0.
 
Zuletzt bearbeitet:
Nein, es geht NICHT einfacher. Mach nicht denselben Fehler wie ich Snow. ^^
Das ist der kleinste deterministische Kreislauf, das kleinste gemeinsame Muster. Alles kompaktere braucht einen Zustand mit 2 Ausgängen.
 
Wieso denn 16 Zustände man braucht doch bloß 12.
Das Problem bei deinem Automaten ist nämlich, dass er z.B. erst den Weg für die Teilbarkeit durch 3 zum Endzustand und dann denn Weg für die Teilbarkeit durch 4 nehmen kann. Dadurch würden auch 7 a's akzeptiert werden.
Aber wie snow schon weiter oben geschrieben hat wiederholen sich die Abstände der Zahlen alle vielfachen von 3*4=12. Also brauchst du 12 Zustände in denen du alle Zahlen die durch 3 oder durch 4 Teilbar sind als Endzustände markierst und einen Kreis vom letzten zum ersten schließt.
 
@Zhak: uuups... stimmt, du hast natürlich recht.

Ich hab meinen Beitrag oben korrigiert. Btw, von q11 kannst du auch gleich wieder in q0 gehen. Da 0 auch durch 3 bzw 4 teilbar ist, ist das dann auch ein Endzustand. Jetzt dürfts aber stimmen
 
Ich bin jetzt zu faul hier groß ne Lösung zu platzieren, aber der von "derlolomat" ist als NEA korrekt, also überführt ihn einfach nach Schema F in einen DEA und ihr habt die Lösung.

Ist manchmal einfacher als einen DEA zu produzieren ;)
Falls der TE nicht weiß wie das geht -> Wandlung NEA nach DEA , dazu gibts genug Erklärungen.

mfg
 
Zurück
Oben