---

Geschrieben von RedHead am 28.05.2007 um 17:12:

  Automat gesucht der mod 3 erkennt

Hab da mal ne frage, ich suche einen autamat DFA oder NFA ist egal der das Eingabe alpahbet {0,1} besitzt und genau die bitzahlen erkennt die durch 3 teilbar sind.

Hat jemand eine Idee wie man das umsetzen kann?

MFg RH

---

Geschrieben von madde am 20.07.2007 um 21:01:

  RE: Automat gesucht der mod 3 erkennt

Schreib dir mal die Zahlen von 0-30 in Binaerform auf und versuche zu erkennen ob die durch drei teilbaren Zahlen ein bestimmtes Muster enthalten und versuche dieses Muster in deinem Automat umzusetzen.

---

Geschrieben von ed209 am 25.07.2007 um 09:29:

 

Angenommen es gibt einen NFA, dann gibt es auch einen DFA.
Also hier der Fall für den DFA:

Mit jeder Eingabe, d. h. mit jeder eingegebenen Zahl landest du in einem bestimmten Zustand. Du kannst aber nicht für jede mögliche Zahl einen Zustand haben (denn es gibt unendlich viele Zahlen und dein Automat ist endlich). Das heißt jeder Zustand steht für eine Klasse von Zahlen.

Jetzt mußt du nur noch herausfinden, für welche Zahlenklassen dein Automat stehen muß. Es gibt da mehrere Lösungen, aber nur eine minmale.

Eins weisst du noch: Alle Zahlen mit denen man in einen akzeptierenden Zustand kommt sind durch drei teilbar. Alle anderen sind es nicht.

Gruß,
ED

---

Geschrieben von RedHead am 04.08.2007 um 12:40:

 

Jup habs rausbekommen, danke schön