ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
 |
|
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
|
|
