Warum ist dieser Automat nicht durch 3 teilbar?

Aufrufe: 54     Aktiv: vor 2 Wochen

0

Hallo zusammen

Warum sagen sie, dass es nicht durch 3 teilbar ist? Ich meine ist doch auch nicht durch 2 teilbar?

10 -> 2

101 -> 5

1011 -> 11

10111 -> 23

Ist doch ne Primzahl, versteh die Lösung nicht!

 

Describe the language recognized by it and prove the correctness of your claim.

This automaton recognizes all strings of binary numbers that are not divisible by 3. To prove

this we need to show that the automaton accepts a string w if and only if it is a binary string

representing a number that is not divisible by 3.

Vielen Dank!

Schöne Grüsse

Sayuri

 

 

 

gefragt vor 2 Wochen
s
sayuri,
Student, Punkte: 82

 
Kommentar schreiben Diese Frage melden
1 Antwort
1

Wo ist denn das Problem? Es geht doch um Teilbarkeit durch 3, nicht durch andere Zahlen und nicht um Primzahlen.

geantwortet vor 2 Wochen
m
mikn
Lehrer/Professor, Punkte: 4.12K
 

Also ich verstehe nicht, wie man auf 3 teilbar kommt, anhand des Automaten

  ─   sayuri, vor 2 Wochen

Ok, aber die obigen Beispiele sind ja keine Gegenbeispiele dazu. Probier Beispiele aus, und schaue nicht(!) in die Lösung (d.h. den Beweis), wenn du etwas lernen willst (und die Aufgabe ist, den Beweis zu finden).

  ─   mikn, vor 2 Wochen

Kannst du mir einen Tipp geben, wie man mit so einem Automaten den Beweis findet bzw. die Vorgehensweise? Hab richtig mühe damit!

  ─   sayuri, vor 2 Wochen

Du wirst die Frage klären müssen, wie sich die Teilbarkeit durch 3 einer binären Zahl ändert, wenn man eine Ziffer anhängt (denn das sind ja die Übergänge im DFA). Dazu probiere Beispiele aus (das hat nichts mit DFA zu tun).

  ─   mikn, vor 2 Wochen
Kommentar schreiben Diese Antwort melden