Discussion:
[S] Pseudo-Code fuer Mealy-Automat
(zu alt für eine Antwort)
Gregor Szaktilla
2014-12-17 04:34:38 UTC
Permalink
Raw Message
Moin allerseits!

In der Hoffnung, hier damit nicht OT zu sein (immerhin möchte ich‘s in C
oder C++ umsetzen):

Ich möchte einen Mealy-Automat implementieren, finde aber keinen
Pseudo-Code, nach dem ich mich richten könnte. Mit der in der Wikipedia
gezeigten Notation (Diagramme mit Pfeilen) kann ich nichts anfangen.

Auch die Suche via Metager war Erfolglos. Ich habe allerdings nicht alle
paar Tausend Fundstellen kontrolliert.

Gruß

Gregor
Stefan Reuther
2014-12-17 11:34:17 UTC
Permalink
Raw Message
Post by Gregor Szaktilla
In der Hoffnung, hier damit nicht OT zu sein (immerhin möchte ich‘s in C
Ich möchte einen Mealy-Automat implementieren, finde aber keinen
Pseudo-Code, nach dem ich mich richten könnte. Mit der in der Wikipedia
gezeigten Notation (Diagramme mit Pfeilen) kann ich nichts anfangen.
Was ist denn das für ein Problem, dessen Lösung "ich brauche einen
Mealy-Automaten" lautet? Ich denk mir zwar öfters "jetzt brauchst du
'nen Zustandsautomaten", aber "jetzt brauche ich einen Mealy-Automaten"
hab ich noch nie gedacht.

Ein Mealy-Automat ist ein Automat, der für seine Ausgabe sowohl die
Eingabe, als auch seinen Zustand auswerten kann. Das könnte man in C
aufschreiben als

typedef .... Input; // Eingabealphabet, Sigma
typedef .... Output; // Ausgabealphabet, Omega
typedef .... State; // Zustand, Q

// Zustandsübergangsfunktion; modifiziert *pState, liefert Ausgabe
Output zeta(State* pState, Input input)
{
// ...
}

(im Gegensatz dazu wäre der Moore-Automat
void delta(State* pState, Input input);
Output lambda(State state);
)

Wie man jetzt die Zustandsübergangsfunktion am zweckmäßigsten
aufschreibt, hängt davon ab, wie der Automat letztlich aussieht (welche
Transitionen man zusammenfassen kann). Das kann sowas
switch (*pState) {
case State_A:
switch (input) {
case Input_A: *pState = State_B; return Output_42;
}
}
sein, oder die beiden switch vertauscht, oder ein Tabellenlookup, oder
eine Formel.


Stefan
Gregor Szaktilla
2014-12-17 17:50:15 UTC
Permalink
Raw Message
Post by Stefan Reuther
Post by Gregor Szaktilla
Ich möchte einen Mealy-Automat implementieren, finde aber keinen
Pseudo-Code, nach dem ich mich richten könnte. Mit der in der Wikipedia
gezeigten Notation (Diagramme mit Pfeilen) kann ich nichts anfangen.
Was ist denn das für ein Problem, dessen Lösung "ich brauche einen
Mealy-Automaten" lautet? Ich denk mir zwar öfters "jetzt brauchst du
'nen Zustandsautomaten", aber "jetzt brauche ich einen Mealy-Automaten"
hab ich noch nie gedacht.
Ein Name wie Mealy kommt mir auch erst in den Sinn, seit ich weiß, dass
man das, was ich suche, wohl so nennt (gelesen habe ich das in der
vorletzten Ausgabe von c't-Hacks).

Soweit ich das verstanden habe, dient ein Mealy-Automat dazu, eine
Impulsfolge in Einsen, Nullen (oder Müll) umzusetzen.
Post by Stefan Reuther
... Das kann sowas
...
sein, oder ...
Danke, das ist ungefähr die Art der Erklärung, die ich auch aus dem
Artikel habe. Dort ging es um das „Lesen“ und „Interpretieren“ des
Signals, das ein DCF-77-Modul absondert (59 Bit plus 1
Synchronisations-Bit in 1 Minute).
Schwierigkeiten habe ich dabei bei der Berücksichtigung
unterschiedlicher (und obendrein nicht so genauer) Zeitfolgen und mit
dem Zerteilen eines Vorgangs in „Zeitschlitze“.

Äh ... mich erinnert das an die Probleme, die ich hatte, als ich
Rekursion verstehen wollte.

Gruß

Gregor
Stefan Reuther
2014-12-18 12:36:50 UTC
Permalink
Raw Message
Post by Gregor Szaktilla
Post by Stefan Reuther
Post by Gregor Szaktilla
Ich möchte einen Mealy-Automat implementieren, finde aber keinen
Pseudo-Code, nach dem ich mich richten könnte. Mit der in der Wikipedia
gezeigten Notation (Diagramme mit Pfeilen) kann ich nichts anfangen.
Was ist denn das für ein Problem, dessen Lösung "ich brauche einen
Mealy-Automaten" lautet? Ich denk mir zwar öfters "jetzt brauchst du
'nen Zustandsautomaten", aber "jetzt brauche ich einen Mealy-Automaten"
hab ich noch nie gedacht.
Ein Name wie Mealy kommt mir auch erst in den Sinn, seit ich weiß, dass
man das, was ich suche, wohl so nennt (gelesen habe ich das in der
vorletzten Ausgabe von c't-Hacks).
Soweit ich das verstanden habe, dient ein Mealy-Automat dazu, eine
Impulsfolge in Einsen, Nullen (oder Müll) umzusetzen.
Ein Mealy-Automat ist ein eher theoretisches Konstrukt: wenn du das, was
du programmiert hast, als Mealy-Automat ausdrücken kannst (also
Eingabe-, Ausgabe- und Zustands-Alphabet sowie Transitionsfunktion),
dann kannst du eben bestimmte theoretische Werkzeuge darauf loslassen.

Zumindest in meiner Praxis ist es deutlich relevanter, dass sich der
Code, den ich da zusammengekloppt habe, als UML-Zustandsautomat
darstellen lässt. Schlicht und ergreifend, weil ich dafür Werkzeuge habe
(z.B. Anzeige statt als Zustandsdiagramm als State/Trigger-Tabelle, um
zu prüfen, ob alle Trigger überall behandelt werden).

Man kann das natürlich umwandeln: so aus der Hüfte geschossen: ein
Mealy-Automat hat die Aktionen (=Ausgabealphabet) an den Transitionen
stehen (und sonst nirgendwo), ein Moore-Automat hat die Aktionen als
"entry"-Aktion an den Zuständen stehen (und sonst nirgendwo).
Post by Gregor Szaktilla
Post by Stefan Reuther
... Das kann sowas
...
sein, oder ...
Danke, das ist ungefähr die Art der Erklärung, die ich auch aus dem
Artikel habe. Dort ging es um das „Lesen“ und „Interpretieren“ des
Signals, das ein DCF-77-Modul absondert (59 Bit plus 1
Synchronisations-Bit in 1 Minute).
Schwierigkeiten habe ich dabei bei der Berücksichtigung
unterschiedlicher (und obendrein nicht so genauer) Zeitfolgen und mit
dem Zerteilen eines Vorgangs in „Zeitschlitze“.
Ich kenne die Schnittstelle des DCF-77-Moduls jetzt nicht, wüsste aber
auch nicht, wo ein Mealy-Automat hier den besonderen Erkenntnisgewinn
bringen könnte. Ich würde ja beginnen mit: auf Start der Minute warten,
ab da die 59 Bits durchzählen :-)


Stefan
Gregor Szaktilla
2014-12-18 18:02:04 UTC
Permalink
Raw Message
...
Danke!

Vielleicht hilft es, wenn ich meine Fragen noch eine Weile in meinem
Kopf kreisen lasse. Seit gestern sind mir einige Kleinigkeiten klar(er)
geworden.

Gruß

Gregor

Loading...