2.2

[etienne]

hi, hab mal ein bischen bei 2.2 herumprobiert, soweit ichs probiert habe passt der automat, aja startpunkt is q0, und endpunkt is q3

grüße etienne

[etienne]

ah hab eine bessere lösung gefunden

δ(q0,0)= q0 2*(0 mod 6) + 0 = 0 mod 6
δ(q0,1)= q1 2*(0 mod 6) + 1 = 1 mod 6
δ(q1,0)= q2 2*(1 mod 6) + 0 = 2 mod 6
δ(q1,1)= q3 2*(1 mod 6) + 1 = 3 mod 6
δ(q2,0)= q4 2*(2 mod 6) + 0 = 4 mod 6
δ(q2,1)= q5 2*(2 mod 6) + 1 = 5 mod 6
δ(q3,0)= q0 2*(3 mod 6) + 0 = 0 mod 6
δ(q3,1)= q1 2*(3 mod 6) + 1 = 1 mod 6
δ(q4,0)= q2 2*(4 mod 6) + 0 = 2 mod 6
δ(q4,1)= q3 2*(4 mod 6) + 1 = 3 mod 6
δ(q5,0)= q4 2*(5 mod 6) + 0 = 4 mod 6
δ(q5,1)= q5 2*(5 mod 6) + 1 = 5 mod 6

von dem kann man sich dann folgendes diagram ableiten, (q0 ist anfangs und endpunkt):

[thoreon]

Hi,

Komme auf den gleichen Automaten mit insgesamt 6 Zuständen.
Mich irritiert aber, dass Fr. Prof. Oswald in der Vorlesung gesagt hat, es geht mit weniger als 6 Zuständen...
Hat jemand dazu einen Ansatz?

Lg
Thomas

[freeye]

da fehlt eine kante von q0 zu q0 mit 0, nicht?

[thoreon]

Hi freeye,
Ja da hast du natürlich recht :-)
Weil es können hinten beliebig viele 0en kommen.
Hab ich beim Vergleichen übersehen - sorry.

Lg
Thomas

[dgb]

Mein Automat schaut ein bisschen anders aus. Start- und Endpunkt sollten verschieden sein, denn sonst funktioniert das Leerwort auch.

[thoreon]

Hi,
stimmt, das Leerwort muss raus...
Beim Startpunkt könnte man noch eine 0-Schleife auf sich selbst einbauen, um führende 0en zu ignorieren...

Lg
Thomas

[etienne]

ah dann war mein erster versuch ja gar ned so bled, kann einfach q5,q6 weglassen ;)

thx @ dgb, wie bist auf den automaten gekommen wenn man fragen darf?


hier noch mal die verbesserte version:

[dgb]

ah dann war mein erster versuch ja gar ned so bled, kann einfach q5,q6 weglassen ;)

thx @ dgb, wie bist auf den automaten gekommen wenn man fragen darf?


hier noch mal die verbesserte version:

Zuerst hab ich den Automaten genau so wie du konstruiert, Start- und Entzustand waren verschieden.
Dann hab ich mir Seite 23 bis 26 im Skriptum durchgelesen, da wird beschrieben wie man endliche Automaten minimieren kann,
sonst wäre ich auch nicht darauf gekommen.
Wenn man diesen Automaten dann minimiert muss man aufpassen, q2 könnte man zum Startpunkt machen, aber dann würde dieser auch führende 0en akzeptieren.

[Zimms]

wie seid ihr eigentlich darauf gekommen, sicherzustellen, dass nur/alle durch 6 teilbaren zahlen akzeptiert werden?

[etienne]

also ich habs so gemacht das ich geschaut hab ob der automat funktioniert für die zahlen von 0-120, und hab dann noch zum test ein paar größere zahlen genommen, und dann hab ich noch ein paar zahlen die nicht durch 6 teilbar sind probiert, naja und das wars ;)

[Chronatog]

Hi

Kann jemand erklären, wie man systematisch vorgeht um festzustellen ob eine Zahl in binärer Darstellung durch eine andere Zahl(im Bsp. 6) teilbar ist?
Vor allem der logische Gedankengang wäre interessant.

[etienne]

so um bei meinem zweiten post anzuschließen
http://www.informatik-forum.at/showpost.php?p=459807&postcount=2

aja als erstes wenn man beim automaten von oben, bei q1 is dann ist man wenn man an der stelle aufhören würde auch in der restklasse eins, bei q2 in der restklasse zwei usw.

ich hab als erstes obigen automaten umgeformt das er \epsilon nicht mehr akzeptiert (Bild1), somit sind anfangs und endpunkt verschieden, sonst gilt für den graphen das selbe wie in dem von meinem zweiten post, wenn man in q1 ist dann und dort aufhört kommt eine zahl raus die in der restklasse 1 von 6 liegt usw.

jetzt hab ich versucht den graphen zu minimieren mit der anleitung aus dem skriptum dabei kommt diese tabelle heraus

\begin{pmatrix}q2 & x \\ q3 & x & x \\ q4 & - & x & x \\ q5 & x & - & x & x \\ q6 & x & x & x & x & x \\ & q1 & q2 & q3 & q4 & q5\end{pmatrix}

man sieht das bei q1,q4 und q2,q5 einträge fehlen somit sind diese paare ununterscheidbar
also mal q5 entfernen und eine schleife auf q2 mit 1 machen(Bild2),
jetzt q4 entfernen und eine verbindung von q2 auf q1 machen mit 0(Bild3)

und das sollte es gewesen sein, jetzt sind die einzelnen punkte natürlich nicht mehr die jeweiligen restklassen

hth

[tonico]

Hi

Kann jemand erklären, wie man systematisch vorgeht um festzustellen ob eine Zahl in binärer Darstellung durch eine andere Zahl(im Bsp. 6) teilbar ist?
Vor allem der logische Gedankengang wäre interessant.

Vereinfacht gesagt, Binärzahlen haben die Eigenschaft, dass wen man eine 0 anhängt die Zahl mit 2 Multipliziert wird, genauso haben Dezimalzahl die Eigenschaft, dass wenn man eine 0 anhängt die Zahl mit 10 multipliziert wird. Hängt man statt einer 0 eine 1 an, dann entspricht das im Binärsystem Zahl * 2 + 1. Will man nun Binärzahlen in Resklassen 0+6Z, ..., 5+6Z einteilen kann man für jede Restklasse einen Zustand definieren. Wir fangen mit 1 an, 1 führt in die Restklasse 1+6Z. Von dieser Restklasse können wir mit einer 0 in die Restklasse 2+6Z mit einer 1 in die Restklasse 3+6Z usw. usf. Da wir nur an Binärzahlen die durch 6 Teilbar sind interessiert sind, muss die Klasse 0+6Z der einzige Endzustand sein. Möglicherweise gibt aber einen einfacheren logischeren Zugang :) .

[a.k]

bei dem beispiel, kann man nicht einfach die falle weglassen? ich meine ohne zu minimieren vom Automat? (ist auch nicht verlangt). Was sagt ihr dazu wenn ich einfach die zustände, aus deren kein weg in einen endzustand führt?

[axestr]

Hallo!

Ein Systematischer Versuch:

b ist eine Binärzahl, die in unserem Fall mit 1 beginnt.
Also ist, wen b n Stellen hat
b = a_n2^n + a_{n-1}2^{n-1} + a_{n-2}2^{n-2} + ... + a_12 + a_0

Dann ist
b \bmod m = ((((((((a_n \bmod m) \cdot 2 + a_{n-1}) \bmod m) \cdot 2 + a_{n-2}) \bmod m) \cdot 2 + \dots + a_1) \bmod m) \cdot 2 + a_0)\bmod m

q0 ist der Startzustand. q0(1) ist vorgegeben, Binärzahlen schreibe ich in Kommata.


d(q0,'1')=q1: Neuer Zustand q1 ~ 1 Rest
d(q1,'0')=q2: '10'+'0' = 2+0 = 2 mod 6 = 2 Rest, neuer Zustand q2 ~ 2 Rest
d(q1,'1')=q3: '10'+'1' = 2+1 = 3 mod 6 = 3 Rest, neuer Zustand q3 ~ 3 Rest
d(q2,'0')=q4: '100'+'0' = 4+0 = 4 mod 6 = 4 Rest, neuer Zustand q4 ~ 4 Rest
d(q2,'1')=q5: '100'+'1' = 4+1 = 5 mod 6 = 5 Rest, neuer Zustand q5 ~ 5 Rest
d(q3,'0')=q6: ' 110'+'0' = 6+0 = 6 mod 6 = 0 Rest, neuer Zustand q6 ~ 0 Rest
d(q3,'1')=q1: '110'+'1' = 6+1 = 7 mod 6 = 1 => q1
d(q4,'0')=q2: '1000'+'0' = 8+0 = 8 mod 6 = 2 => q2
d(q4,'1')=q3: '1000'+'1' = 8+1 = 9 mod 6 = 3 => q3
d(q5,'0')=q4: '1010'+'0' = 10+0=10 mod 6 = 4 => q4
d(q5,'1')=q5: '1010'+'1' = 10+1=11 mod 6 = 5 => q5
d(q6,'0')=q6: '00'+'0' = 0+0=0 mod 6 = 0 => q6
d(q6,'1')=q1: '00'+'1' = 0+1=1 mod 6 = 1 => q1
Endzustand ist q6.

Ich bin so vorgegangen:
d(q0,'1') muss es laut Angabe geben, und das hat 1 Rest, also führe ich den neuen Zustand q1 ein und sage d(q0,'1')=q1. q1 kann wieder mit {0,1} kombiniert werden:
d(q0,'1')=q1: Neuer Zustand q1 ~ 1 Rest
d(q1,'0')=? :
d(q1,'1')=? :

Jetzt wird die nächste Stelle geholt. Weil q1 1 Rest hat, und mit 2 Multipliziert wird, schreibe ich '10', und addiere je nach dem '0' oder '1'.
d(q1,'0')=?: '10'+'0' = 2+0 = 2 mod 6 = 2 Rest
d(q1,'1')=?: '10'+'1' = 2+1 = 3 mod 6 = 3 Rest
Für 2 Rest und 3 Rest gibt es noch keinen Zustand, als führt man q2, q3 ein.

Und so weiter bis zum bitteren Ende, für Modulo m hat man dann m+1 Zustände.

Man muss der Verlockung widerstehen und q0 nicht als Endzustand verwenden, sonnst wäre die Sprache {0,1}*, wir brauchen aber 1{0,1}*.

Den Automaten muss man dann halt noch minimalisieren, wie schon hier erwähnt.

Lg Axl.

[VR1]

ah hab eine bessere lösung gefunden

δ(q0,0)= q0 2*(0 mod 6) + 0 = 0 mod 6
δ(q0,1)= q1 2*(0 mod 6) + 1 = 1 mod 6
δ(q1,0)= q2 2*(1 mod 6) + 0 = 2 mod 6
δ(q1,1)= q3 2*(1 mod 6) + 1 = 3 mod 6
δ(q2,0)= q4 2*(2 mod 6) + 0 = 4 mod 6
δ(q2,1)= q5 2*(2 mod 6) + 1 = 5 mod 6
δ(q3,0)= q0 2*(3 mod 6) + 0 = 0 mod 6
δ(q3,1)= q1 2*(3 mod 6) + 1 = 1 mod 6
δ(q4,0)= q2 2*(4 mod 6) + 0 = 2 mod 6
δ(q4,1)= q3 2*(4 mod 6) + 1 = 3 mod 6
δ(q5,0)= q4 2*(5 mod 6) + 0 = 4 mod 6
δ(q5,1)= q5 2*(5 mod 6) + 1 = 5 mod 6

von dem kann man sich dann folgendes diagram ableiten, (q0 ist anfangs und endpunkt):

Ich war das letzte mal nicht in der Vorlesung, aber wie kommst du aus obiger Tabelle auf einen Automaten???
Und warum nimmst du jeden modolo-Tupel Mal 2?