endlichen Automaten basteln :(

[Karl Pech]

Hallo Leute,

Ich kämpfe im Moment mit folgender Aufgabe und weiß keinen Ansatz:
~~~
Es sei L = {bin(n)^R | n aus |N und 3 teil n}, wobei zum Wort
x = x_1...x_n mit x^R = x_n...x_1 die Spiegelung von x bezeichnet wird.

(a) Konstruieren Sie einen DEA, der genau die Wörter der Sprache L akzeptiert.
(b) Geben Sie eine reguläre Grammatik G für die Sprache L an. Beweisen Sie:
L = L(G).
~~~

Zu (b) habe ich im Moment gar keine Ideen, aber zu (a) habe ich 'was im "Netz der
Netze" entdeckt, nämlich das eine Binärzahl genau dann durch 3 teilbar ist, wenn
ihre alternierende Summe durch 3 teilbar ist. Leider wußte ich vorher nicht, ob
damit auch Summen gemeint sind, die von rechts nach links gebildet werden. Deshalb
habe ich ein kleines Delphi-Programm dazu geschrieben, welches mir das Ganze verdeutlichen
sollte: http://offskat-game.sf.net/test.zip . Nach dem Ergebnis zu urteilen, daß mir dieses
Programm geliefert hat, würde ich sagen, daß es keinen Unterschied macht von welcher Seite
addiert wird. Im Übrigen müßte ich nun einen DEA finden, dessen Zustandsübergangsfunktion
d im Grunde so ähnlich definiert ist d(z, x) := (z, alternierende_Summe(x)). Diese Funktion befindet
sich in der Datei myunit.pas. Allerdings ergeben sich hier Schwierigkeiten, denn
wie soll ich die Rekursivität von alternierende_Summe auf d übertragen und wie soll ich die
eigentlichen Rechenoperationen in alternierende_Summe auf d übertragen?


Vielen Dank!


Viele Grüße
Karl

[Martin Fuchs]

Post by Karl Pech
~~~
Es sei L = {bin(n)^R | n aus |N und 3 teil n}, wobei zum Wort
x = x_1...x_n mit x^R = x_n...x_1 die Spiegelung von x bezeichnet wird.

Ok, ohne genau auf die Aufgabe einzugehen und was zu deiner u.g.
Idee zu schreiben, stelle ich dir mal einen Vorschlag vor, wie
du einen Automaten konstruierst, der alle durch 3 teilbaren Binärzahlen
akzeptiert.

Der Automat hat 4 Zustände,

q_s, Startzustand, wird benötigt, da das leere Wort nicht akzeptiert
werden darf

q_0 =^= 0 (mod 3)
q_1 =^= 1 (mod 3)
q_2 =^= 2 (mod 3)

Für die Zustandsübergänge kann man sich folgendes übelegen

(1) Wenn wir in q_0 sind, hat die bisher gelesene Zahl die
Form 3*k (für irgendein natürliches k); falls wir eine "0"
lesen (= Multiplikation mit 2), bleiben wir in q_0, beim
Lesen einer "1" (= 2 * (3k) + 1) gehen wir in q_1

(2) Wenn wir in q_1 sind, hat die bisher gelesene Zahl die
Form 3*k+1; falls wir eine "0" lesen, gehen wir in q_2, beim
Lesen einer "1" (= 2 * (3k+1) + 1) gehen wir in q_0

Die Zustandsübergänge von q_2 überlasse ich dir zur Übung.

Ich denke, dass dieser Ansatz wesentlich einfacher ist,
als die Idee mit der alternierenden Quersumme.

Post by Karl Pech
L = L(G).

Naja, wenn du den Automaten hast, benutzt du eben das Standardvefahren
du weiß ja, wo du das findest ;-), um daraus eine Grammatik zu
konstruieren. Da ist dann eigentlich nichts mehr zu beweisen, da das
Verfahren allgemein verifiziert ist, aber ein expliziter Beweis ist
meist auch nicht schwer.

mf

[Hannes Petersen]

Post by Karl Pech
~~~
Es sei L = {bin(n)^R | n aus |N und 3 teil n}, wobei zum Wort
x = x_1...x_n mit x^R = x_n...x_1 die Spiegelung von x bezeichnet wird.
(a) Konstruieren Sie einen DEA, der genau die Wörter der Sprache L akzeptiert.
L = L(G).
~~~

Diese Frage ist wohl schon so oft gestellt worden, dass dir schwerlich

Post by Karl Pech
Zu (b) habe ich im Moment gar keine Ideen,

Nimm den Automaten aus (a) und bastle eine Grammatik daraus.
Direkt geht aber einfacher.

Post by Karl Pech
aber zu (a) habe ich 'was im "Netz der
Netze" entdeckt, nämlich das eine Binärzahl genau dann durch 3 teilbar ist, wenn
ihre alternierende Summe durch 3 teilbar ist. Leider wußte ich vorher nicht, ob
damit auch Summen gemeint sind, die von rechts nach links gebildet werden.

Worin besteht denn der Unterschied zwischen den Summen?
(Dies ist keine rhetorische Frage. Bitte beschreibe mir den
Unterschied der Summen)

Post by Karl Pech
Deshalb
habe ich ein kleines Delphi-Programm dazu geschrieben, welches mir das Ganze verdeutlichen
sollte: http://offskat-game.sf.net/test.zip . Nach dem Ergebnis zu urteilen, daß mir dieses
Programm geliefert hat, würde ich sagen, daß es keinen Unterschied macht von welcher Seite
addiert wird.

Die Summen müssten in einem Drittel aller Fälle unterschiedlich sein.
(Ob das einen Unterschied macht ist eine andere Frage.)

Post by Karl Pech
[...]

Dein Ansatz muss schief laufen, da EAs im Allgemeinen keine Summen
bilden können.

Du könntest folgende Überlegungen anstellen: Eine Zahl ist durch 3
teilbar, wenn ihre Quersumme durch 3 teilbar ist. Und wann ist die
Quersumme durch drei teilbar? Na logisch, wenn deren Quersumme durch
drei teilbar ist. Und die wiederum, wen deren Quersumme, also die
Quersumme der Quersumme der Quersumme durch drei teilbar ist. Du
ermittelst also so lange Quersummen der Quersummen, bis die Zahl
einstellig ist. Das geht, weil die Quersumme einer mehrstelligen Zahl
weniger Stellen hat als die Zahl selbst. Die ganze Prozedur ist eine
Abbildung (im mathematischen Sinne) einer beliebigen Zahl auf eine
einstellige. Nun gibt es aber nur begrenzt viele einstellige Zahlen,
nämlich genau zehn (im Dezimalsystem. Im Binärsystem geht es nur bis
auf zwei Stellen herunter; es gibt also vier Möglichkeiten).
Spätestens hier könnte dir aufgehen, dass du gar keine Summen
ausrechnen musst, sondern die (beliebigen) Zahlen nur geschickt auf
die maximal zehn Ziffern abzubilden brauchst. Direkt. Von hier ist der
Gedanke nicht mehr weit zum Restklassensystem: Es gibt (bezüglich der
Teilbarkeit durch 3) genau drei verschiedene Sorten (Klassen) von
Zahlen:
- Die, die beim Teilen den Rest 0 ergeben, also die Zahlen, die glatt
durch drei teilbar sind.
- Die, die Rest eins hinterlassen.
- Und die, die Rest zwei übrig lassen.

Du muss jetzt nur noch rauskriegen, von welcher Klasse eine Zahl in
welche andere wandert, wenn man eine bestimmte Ziffer davor (bzw
dahinter) hängt. Alle Zahlen einer Klasse müssen sich gleich
verhalten. Die Zahlen {1,4,208,179623} gehören alle in die Klasse
"Teilt 3 mit Rest 1". Wenn man eine zwei dranhängt, fallen sie alle in
die Klasse "Teilt 3 glatt".

Das musst du nun noch für alle Übergänge ausarbeiten und auf das
Binärsystem übertragen.

/Hannes

[Karl Pech]

Hallo Hannes,

Post by Hannes Petersen
Worin besteht denn der Unterschied zwischen den Summen?
(Dies ist keine rhetorische Frage. Bitte beschreibe mir den
Unterschied der Summen)

Also ich dachte bisher, daß es da im Ergebnis keinen Unterschied geben sollte,
jedenfalls hat mir dies auch mein Programm bis zur Grenze von 10000 bestätigt
(habe ich überprüft, in "out.txt" war die Grenze jedoch kleiner gewählt).

Auch in der Aufsummierung scheint es keinen Unterschied zu geben:

Quersumme von links:
|+1-1+0-1+1-1+0-1+0-1| = |-11| = 11 --> |+1-1| = 0

Quersumme von rechts:
|+1-0+1-0+1-1+1-0+1-1| = |+11| = 11 --> |+1-1| = 0

Der einzige Unterschied ergibt sich bei diesem Beispiel im verschiedenen Vorzeichen,
das wegen der Betragsstriche jedoch ohne Bedeutung ist, oder?



Viele Grüße
Karl

[Hannes Petersen]

Hannes Petersen schrieb>

Post by Hannes Petersen
Worin besteht denn der Unterschied zwischen den Summen?

Der einzige Unterschied ergibt sich bei diesem Beispiel im verschiedenen Vorzeichen,
das wegen der Betragsstriche jedoch ohne Bedeutung ist, oder?

Hmpff. Wie ich sagte: Ob es bezüglich der Teilbarkeit etwas ausmacht
ist eine andere Frage, aber gleich sind die Ergebnisse vor der
Betragnahme nicht. Klar, das ist Korinthenkackerei, aber wir reden
hier schließlich über Mathematik bzw. Informatik, oder?

Du hast hier noch kein Erfolgs-"Aha!" gepostet, also nochmal zum
Automaten (allerdings wieder im Dezimalsystem):

Löse dich endlich davon, mit einem EA eine Quersumme auszurechnen. Ein
EA kann nicht rechnen, auch nicht summieren. In meinem letzten Beitrag
habe ich dir eine Möglichkeit gegeben, wie du von der Quersumme zu den
Restklassen kommst. Tut mir leid, wenn ich mich nicht verständlich
machen konnte; die Kurzform meiner Aussage ist folgende: Scheiß auf
die Quersummenbildung, damit kommst du nicht weiter.

Also nochmal: Denke dir eine beliebige Zahl: 7426358 (OBdA)

Ein EA kann, wie gesagt nicht rechnen, er kann sich aber Sachverhalte
in Zuständen merken. Er kann auch nur ein Zeichen (eine Ziffer) pro
Schritt verarbeiten; lassen wir ihn vorne anfangen, er liest also der
Reihe nach 7,4,2,6,3,5 und 8. Bei jeder gelesenen Ziffer kann er in
einen anderen Zustand übergehen. Die Zustände "teilt 3" und "teilt
drei nicht" reichen nicht aus. Du brauchst mindestens drei Zustände
(ich nehme hier sogar 4 Zustände):
A: bisher nichts gelesen (Endzustand, oder?)
B: bisher gelesene Zahl ergibt Rest 1 bei einer Teilung durch 3. (Kein
Endzustand)
C: bisher gelesene Zahl ergibt Rest 2 bei einer Teilung durch 3. (Kein
Endzustand)
D: bisher gelesene Zahl ist glatt durch 3 teilbar. (Endzustand!)

Wenn du bisher nicht verstanden hast, warum du genau diese Zustände
brauchst, kann ich dir nicht weiterhelfen; wie man auf genau diese
Idee kommt, ist nicht lehrbar. Nimm diese Zustände mal als gegeben an.

Mal sie als Graph oder lege eine entsprechende Übergangsmatrix an.

Der EA startet im Zustand A und liest die Ziffer 7; danach befindet er
sich in Zustand B, weil die bisher gelesene Zahl (die Zahl 7) geteilt
durch 3 2Rest1 ergibt. Du trägst also A--7->B in den Graphen (oder
entsprechendes in die ÜM ein). Du kannst auch gleich alle Verbindungen
eintragen, wenn die erste Ziffer eine 1,...,9 ist. Wenn ich dich
richtig verstanden habe möchtest du führende Nullen als "bisher keine
Zahl eingelesen" verstanden wissen, also fügst du auch noch "A--0->A"
ein.

So, nun liest der EA die 4 ein. Was passiert mit der Zahl, die er
bisher gelesen hat? Klar: aus der 7 wird eine 74. Rechentechnisch
passiert also Folgendes: 7*10+4=74 (Hier steht die 10, weil ich wie
gesagt das Dezimalsystem benutze). Verallgemeinert passiert Folgendes:
(d1+1)*10+(d2+1)=r, hierbei bezeichnet dx eine beliebige Zahl, die
glatt durch drei teilbar ist. Wie kann man nun das Resultat r
vereinfachen? r = (d1+1)*10+(d2+1) = d1*10+10+d2+1 = (d1*10+d2+9)+2 =
d3+2. Die Klammer in der vorletzten Formel ist eine Zahl, die glatt
durch drei teilbar ist, also habe ich sie d3 genannt.

Diese Verallgemeinerung ist wichtig, weil sie die Begründung ist, auf
die ganze Idee basiert. Auf deutsch ausformuliert heißt die Formel:
Wenn du an irgendeine Zahl, die beim Teilen durch 3 Rest 1 ergibt,
eine Ziffer dranhängst die beim Teilen durch 3 ebenfalls den Rest 1
ergibt, dann bekommst du (im Dezimalsystem) eine Zahl heraus, die beim
Teilen durch 3 den Rest 2 ergibt.
Du kannst also in den Graphen die Kanten: B--1->C, B--4->C, B--7->C
eintragen.

Was wäre passiert, wenn der Automat im Zustand B eine 2, 5 oder 8
gelesen hätte?
Die Rechnung würde lauten: r = (d1+1)*10+(d2+2) = d1*10+10+d2+2 =
(d1*10+d2+12) = d3. Oh!, das Resultat wäre glatt durch drei teilbar
gewesen. Also kommen die Kanten B--2->D, B--5->D, B--8->D auch dazu.

Wenn du für jeden Zustand alle zehn Kanten eingetragen hast, bist du
fertig. Für einen EA, der Binärzahlen einliest, ist die Arbeit um den
Faktor fünf einfacher, aber du weist ja nun, wie es geht und wie es
sich begründet.

/Hannes

[Karl Pech]

Hi Leute,

Erstmal: Danke für eure Ideen!

Post by Hannes Petersen
Du hast hier noch kein Erfolgs-"Aha!" gepostet

Hab' mich jetzt aus Frust nochmal mit dieser Aufgabe beschäftigt
(obwohl der Übungszettel schon nicht mehr aktuell ist) und hatte plötzlich einen
Moment der "Erleuchtung"!!! :))

Also hier ist die Idee:

Zunächst einmal darf der Automat keine führenden Nullen einer Zahl akzeptieren.
Nehmen wir also an wir befinden uns in einem Anfangszustand a und lesen nun
eine Zahl von links nach rechts ein. Solange wir Nullen einlesen bleiben wir in a.
Lesen wir jetzt eine 1, so gehen wir in Zustand Rest_1, den 1 % 3 = 1. Von hier aus
gibt es zwei Möglichkeiten:

1.) Wir lesen eine 0: Also 10_2 = 2_10 % 3 = 2. Wir gehen in Zustand Rest_2.
2.) Wir lesen eine 1: Also 11_2 = 3_10 % 3 = 0. Wir gehen in Zustand Rest_0.

Damit haben wir alle Möglichkeiten von Zustand Rest_1 wegzukommen betrachtet.
Außerdem haben wir alle Möglichkeiten von Zustand a wegzukommen betrachtet.
Offenbar ist der Zustand Rest_0 Endzustand, weil wir ja dort gelandet sind, nachdem
wir eine 3 gelesen hatten.

Welche Möglichkeiten gibt es nun von Rest_0 wegzukommen?

1.) Wir lesen eine 0: Also 110_2 = 6_10 % 3 = 0. Wir bleiben in Rest_0.
2.) Wir lesen eine 1: Also 111_2 = 7_10 % 3 = 1. Wir gehen zurück zu Rest_1.

Welche Möglichkeiten gibt es nun von Rest_2 wegzukommen?

1.) Wir lesen eine 0: Also 100_2 = 4_10 % 3 = 1. Wir gehen zurück zu Rest_1.
2.) Wir lesen eine 1: Also 101_2 = 5_10 % 3 = 2. Wir bleiben in Rest_2.

Damit haben wir alle Möglichkeiten von einem beliebigen Zustand zu einem Anderen zu kommen
gefunden. Wir sind also fertig! Der Automat akzeptiert allerdings keine 0_2, denn eigentlich
gilt ja 0_2 % 3 = 0.

Im Grunde genommen hat es also gereicht folgende Fälle zu betrachten um den Automaten zu
konstruieren:
1, 2, 3, 4, 5, 6, 7. Frag' mich nur, ob das jetzt Zufall ist. Andererseits fällt einem auf,
daß es genau 2^3(!) - 1 Fälle sind. Hmmm ... :)


Also eigentlich müßte sich nun jeder DEA zu einer Problemstellung wie
"Geben Sie einen DEA M = (Z, \Sigma, \delta, z_0, E) mit \Sigma = {0,1} und
L(M) = {x \in \IN-{0} : k teilt x mit k \in \IN-{0,1}} an."

Folgendermaßen lösen lassen:

Wir gehen von einem Anfangszustand a aus. Wir "überlesen" führende Nullen. Bei einer 1
geht's in Rest_1. Anschließend immer probiert man von jedem Zustand Rest_i alle Möglichkeiten
also 0 oder 1 durch und schaut welche Zahl man bisher so aufgebaut hat. In jedem Fall hat man
wohl insgesamt k-1 "Rest_i"-Zustände(, da (k-1) % k = k-1 aber k % k = 0 und dann wiederholt sich
alles für Zahlen > k) mit A zusammen also k Zustände. Da muß man dann also alle Möglichkeiten
durchprobieren.


Viele Grüße
Karl

[Karl Pech]

Hi Leute,


Inzwischen haben wir die Aufgaben in der Übungsgruppe besprochen und
folgenden Automaten als Lösung bekommen:

Loading Image...

Leider verstehe ich diesen Automaten dennoch nicht.

Es ist mir jetzt klar, daß die 2er-Potenzen sich bei der
Modulo-Operation periodisch abwechseln:

2^0 mod 3 = 1
2^1 mod 3 = 2
2^2 mod 3 = 1
.
.
.

Klar ist auch, daß die führenden Nullen (oder eine Null) ausgeschlossen werden müssen,
da wir die Null nicht zu den natürlichen Zahlen zählen. Braucht man also deshalb 4 Zustände?
Den Anfangszustand, der das mit den "führenden Nullen" klärt, einen Zustand für Rest 0,
einen für Rest 1 und Rest 2 ?


Und was danach folgt (also die Anordnung der Zustände) verstehe ich dann nicht mehr. Wo ist da
der Bezug zu der oberen Gesetzmäßigkeit? Wie kommt man gerade auf eine solche Anordnung der
Zustände? Ich sehe nur, daß q_0, q_1, q_4 zu einem gültigen Wort führt, wenn es eine gerade Anzahl
von Einsen enthält und eventuell eine gerade Anzahl von Nullen, wobei Einsen zwischen diesen Nullen
übersprungen werden, oder?
So, jetzt habe ich die Funktionsweise des Automaten zwar umgangssprachlich "beschrieben" aber nicht
erkannt. :(


Danke für eure Hilfe!


Grüße
Karl

[Martin Fuchs]

Post by Karl Pech
Inzwischen haben wir die Aufgaben in der Übungsgruppe besprochen und
http://offskat-game.sf.net/dea.gif

Das ist doch genau das Prinzip, dass ich dir in meinem Posting
vom 24.10.04 erklärt habe. Du hättest es bloß auf das "gespiegelte
Wort" umbrechen sollen.

Post by Karl Pech
Klar ist auch, daß die führenden Nullen ausgeschlossen werden müssen,
da wir die Null nicht zu den natürlichen Zahlen zählen.

Unfug.

1. Ob die 0 eine natürlich Zahl ist oder nicht, hängt vom Dozenten ab.

2. Die "führenden Nullen", die dein Automat liest, sind doch
in Wirklichkeit schließende Nullen, du sollst ja schließlich
in Abhängigkeit vom /gespiegelten/ Wort akzeptieren.
Und schließende Nullen sind nun eben nicht relevant, wie man sich leicht überlegt,
denn
3k * 2 = 3k'
(3k+1)*2 = 3k' + 2
(3k+2)*2 = 3k' + 1

Daraus sieht man nämlich einerseits, dass falls ein Wort w akzeptiert werden würde,
auch das Wort w00...0 akzeptiert werden würde. Andererseits ändert das Anhängen
schließende Nullen an nicht-akzeptierte Wörter auch nichts daran, dass diese
nicht akzeptiert werden.

Post by Karl Pech
Und was danach folgt (also die Anordnung der Zustände) verstehe ich dann nicht mehr. Wo ist da
der Bezug zu der oberen Gesetzmäßigkeit?

siehe mein erstes Posting.


mf

[Bernd Post]

Martin Fuchs wrote:
[...]

Post by Martin Fuchs
Unfug.
1. Ob die 0 eine natürlich Zahl ist oder nicht, hängt vom Dozenten ab.

[...]

0 war in der alten DIN natürlich ist aber seit geraumer Zeit
unnatürlich. Auf jeden Fall wird sie sich nicht für Dozenten verbiegen ;-)
N vereinigt 0 = N index 0

SCNR
Bernd

[Martin Fuchs]

Post by Bernd Post
0 war in der alten DIN natürlich ist aber seit geraumer Zeit
unnatürlich.

Es ist ja wohl völlig lächerlich, Mathematik mittels DIN
zu formalisieren.


mf

[Bernd Post]

Post by Martin Fuchs
Es ist ja wohl völlig lächerlich, Mathematik mittels DIN
zu formalisieren.

Nun dazu einige Hinweise,

-Mir persönlich ist es lieber die natürlichen Zahlen werden zentral
definiert, als das jeder für sich entscheidet was zur Menge gehört oder
nicht. Lächerlicher als ein Professor beliebiger Qualität der Definiert
ist es IMO jedenfalls nicht.
(Und erspart einem hoffentlich irgendwann die Frage welchen Professor
Autor XY gehabt hat)

-Der OP schrieb
"Klar ist auch, daß die führenden Nullen ausgeschlossen werden müssen,
da wir die Null nicht zu den natürlichen Zahlen zählen."

Wobei ich das "wir" als entscheidend ansehe, im normalen Sprachgebrauch
fällt das Wort eher raus, insofern denke Ich der OP wollte damit
ausdrücken, daß sein Professor die natürlichen Zahlen als Menge ohne 0
ansieht.

Ansonsten hoffe Ich, daß du mein vorherige Posting nicht für zu ernst
genommen hast, für einen Streit wäre das echt zu dünn ;-)

Grüße
Bernd

[Johann Deutinger]

Post by Bernd Post
0 war in der alten DIN natürlich ist aber seit geraumer Zeit
unnatürlich. Auf jeden Fall wird sie sich nicht für Dozenten
verbiegen ;-) N vereinigt 0 = N index 0

Hallo Bernd,

welche DIN-Norm sagt das? Gibts dazu eine Quelle im Internet?

Danke,
Johann

[Bernd Post]

Post by Johann Deutinger
Hallo Bernd,
welche DIN-Norm sagt das? Gibts dazu eine Quelle im Internet?
Danke,
Johann

Und schon der eigenen Erinnerung zum Opfer gefallen, die Null ist nach
DIN 5473 Teil der natürlichen Zahlen, Asche auf mein Haupt.

Grüße
Bernd