DEA der Binärdarstellung aller Zahlen i akzeptiert, wenn diese durch 5 teilbar sind

4 Antworten

Vom Fragesteller als hilfreich ausgezeichnet
Schachpapa
29.10.2013, 23:34 
Zustand    Eingabe  Folgezustand
0            0            0
0            1            1
1            0            2
1            1            3
2            0            4
2            1            5
3            0            1
3            1            2
4            0            3
4            1            4

Vgl. Bild
DEA - (Computer, Technik, Informatik)
Schachpapa  29.10.2013, 23:38

Im Bild habe ich den Übergang von Z3 bei Eingabe 1 nach Z2 vergessen, sorry.

0
cg1967  31.10.2013, 21:37
@Schachpapa

Und in der Tabelle bei Zustand 2 Eingabe 1 das modulo 5. ;) (Im Bild ists korrekt.)

1
Schachpapa
29.10.2013, 20:31

Du hast 5 Zustände, die den jeweiligen Rest repräsentieren. Von jedem Zustand gibt es je einen Übergang bei 1 zu einem anderen und einen bei 0. Eine angehängte 0 entspricht einer Multiplikation mit 2, sie führt dich z:b. von Zustand 3 in Zustand 1 (weil 3 * 2 = 5 + 1). Eine angehängte 1 entspricht einer Multiplikation mit 2 plus Addition von 1, das würde dich von Z4 wieder nach Z4 führen (weil 4*2+1 = 9 = 5 + 4). Das machst du für alle Zustände. Der Zustand 0 ist Start- und Endzustand.
prof2910 
Fragesteller
 29.10.2013, 20:46

Hallo, danke für die Antwort. Leider blicke ich irgendwie immer noch nicht so durch. Kannst du es nochmal ausführlicher erklären? Sorry.

0
cg1967
31.10.2013, 21:35

Hm, sollt Du nicht eher einen endlichen Automaten konstruieren, der auf Teilbarkeit durch 5 prüft? Dazu liest Du die Zahl vom MSB aus ein und triggerst abhängig vom vorherigen Zustand den nächsten: Anfangszustand 0. Neuer Zustand = (Zustand * 2 + Bitwert) % 5.

Erläuterung: Durch einlesen des nächsten Bits verdoppelt sich der bisherige Restwert (aus dezimal 1 % 5 = 1 wird 2 % 5 = 2), bei eingelesener 1 erhöht er sich zusätzlich um 1. Restwerte > 4 brauchen nicht beachtet zu werden. So kommst Du auf die Zustandsübergangstabelle von Schachpapa, wobei da für Zustand 2 Eingabe 1 der Folgezustand 0 sein muß..
TomRichter
29.10.2013, 19:55

Nach jedem eingegebenen Zeichen die bisher eingegebene Zeichenfolge in eine Zahl umrechnen und den Divisions-Rest bestimmen.

prof2910 
Fragesteller
 29.10.2013, 20:03

Ok, vielen Dank; kannst du das vielleicht noch etwas genauer ausführen? Danke.

0
cg1967  31.10.2013, 22:00

Hallo Tom,

genau dies soll der Automat ja machen. In Pseudocode sieht das so aus:

function CheckDivisibility(Zahl_in_Binaerdarstellung as String, Divisor as Integer) : Teilbar as Boolean
var Rest Integer = 0
for i = 0 to length(Zahl_in_Binaerdarstellung) do
    Rest = (Rest * 2 + Zahl_in_Binaerdarstellung[i]) % Divisor
next
Teilbar = (Rest = 0)
end function

Die Werte, welche darin Rest einnehmen kann, sind die Zustände des endlichen Automaten.

1
TomRichter  01.11.2013, 15:46
@cg1967

Vielleicht hast Du die Aufgabe richtig interpretiert, und es geht um einen Automat, der beliebig lange Eingaben akzeptiert, die den Wertebereich einer int64 überschreiten.

Das wäre dann aber weniger Thema endlicher Automat und mehr Mathematik und Restklassen.

Für kleinere Eingaben gibt es eingebaute Methoden zur Wandlung:

Convert.ToInt64(ZahlinBinaerdarstellung, 2)

Damit lässt sich der mathematische Teil erschlagen, bleibt nur noch der Automatenteil der Aufgabe.

1