Determinitischer EA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:28 Sa 22.11.2008 | | Autor: | csak1162 |
| Aufgabe | Geben Sei einen DEA für die folgende Sprache über dem Alphabet {0,1} an:
Die Menge aller Zeichenketten, die mit 1 beginnen und kongruent 0 modulo 3 sind, wenn die Zeichenketten als Binärdarstellung einer ganzen Zahl interpretiert werden. |
ich hab jetz mal eine liste von zahlen die durch drei teilbar sind aufgeschreiben
ich erkenne ein muster
3 11
6 110
12 1100
24 11000
dann mit
9 1001
18 10010
36 10010
15 1111
30 11110
60 111100
usw..
das geht immer so weiter, aber wie hilft mir das??
es ist auch nicht immer eine gerade anzahl an 1ern
z.b
21 10101
42 101010
84 1010100
weiß jemand wie man das dann hinzeichnen kann???
danke lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:46 So 23.11.2008 | | Autor: | bazzzty |
Ist nicht ganz leicht, Dir da einen Tipp zu geben, ohne die ganze Aufgabe zu lösen. Ich gebe Dir mal eine Teilbarkeitsregel für Zahlen in Dualdarstellung:
"Eine Binärzahl ist durch drei teilbar, genau dann, wenn die Anzahl
der Einsen an geraden Stellen und die Anzahl der Einsen an ungeraden Stellen kongruent modulo 3 sind."
Das sollte zum einen reichen, um einen Automaten mit 7 Zuständen anzugeben (geht es mit weniger?), der die Aufgabe löst, zum anderen sollte es Dich anregen, über die Regel nachzudenken. Die Grundlagen dafür sollten die ersten Wochen Mathestudium gelegt haben (Restklasseringe). Vielleicht auch eine Gelegenheit, darüber nachzudenken, wie andere Teilbarkeitsregeln mit Restklasseringen zusammenhängen.
|
|
|
|
