Merkmale Statemaschine

[Achim S. (achims)]

Hallo
Gibt es klassische Merkmale für eine Statemaschine bzw um sie zu 
erkennen und die Funktion nach vollziehen zu können?
z.B. die Verwendung von switch und case und kein delay ?
oder noch andere "einfache" Merkmale?
achim

[Norbert M. (Gast)]

Achim Seeger schrieb:
> Gibt es klassische Merkmale für eine Statemaschine bzw um sie zu
> erkennen und die Funktion nach vollziehen zu können?

Ich bin zwar nicht vom Fach, mir würden aber zwei Merkmale einfallen:
- Es gibt definierte Zustände.
- Es gibt definierte Übergänge zwischen diesen Zuständen.

> z.B. die Verwendung von switch und case und kein delay ?

Das ist überhaupt kein Merkmal und hilft wohl auch kaum.
Eine Filterkaffeemanschine könnte man zum Beispiel mit zwei Zuständen 
beschreiben, nämlich (A) "Schalter ein" oder (B) "Schalter aus". 
Zwischen diesen Zuständen gibt's auch nur zwei Übergänge, nämlich A -> B 
und B -> A.
Das ganze kann man jetzt beliebig weit mathematisch aufdröseln.
Man kann sich beliebige Maschinen ausdenken, mit beliebig vielen 
Zuständen und Übergängen. Da kann man sicher auch switchen und delayen.

> oder noch andere "einfache" Merkmale?

Wo soll denn die Reise hingehen?

Gruß, N.

[J. V. (janvi)]

eine notwendige Voraussetzung (in HW) ist, daß ein Ausgang wieder auf 
einen Eingang der Logik zurückgeführt wird. Ab dem Moment kann das 
Verhalten nicht mehr durch eine einfache boolsche Gleichung beschrieben 
werden, weil es die Zustände "davor" und "danach" gibt. "switch" und 
"case" klingt aber eher nach Software ? wo man natürlich auch 
Statemachines sinnvoll zusammenbauen kann. Das muß aber nicht sein. 
Oftmals entstehen in der SW auch ungwollt Statemachines die zu einem 
ebenfalls ungewollten Dead-Lock führen können. Da hilft nur ein sauberes 
Design (anstelle von Reverse Engineering im Problemfall)

[Kindergärtner (Gast)]

Das ist ganz hart mathematisch eindeutig definiert: 
http://de.wikipedia.org/wiki/Endlicher_Automat   ("State Maschine" ist 
ja nur das englische Wort dafür)

Zitat: "Ein Automat heißt endlich, wenn die Menge der Zustände, die er 
annehmen kann (später S genannt), endlich ist." Insbesondere ist jede 
Digitalschaltung einer, und damit jede CPU. Programme betrachtet man zu 
theoretischen Beweiszwecken als Turingmaschinen, obwohl sie eigentlich 
keine sind, da der Speicher im Endeffekt doch endlich ist (wenn auch 
groß).

[Achim S. (achims)]

Hallo
Es geht dabei um Software.
Die Beispiel (einfach) die ich bisher gefunden und verwendet habe laufen 
fast immer nach dem gleichen Schema (vereinfacht)

void task 1
{ tu was }

void task 2
{
switch (Zahl)
case (Zahl)
tu was
break
case (Zahl)
was anderes
break
}

while(1)
task 1
task 2
return

Dabei wird durch den Aufruf der task immer wieder die void aufgerufen. 
Innerhalb der void können die verschiedenen Teile ausgeführt werden. Es 
können noch viele Stufen eingefügt werden. Dadurch habe ich zu dem jedem 
Aufruf von task immer en nachfolgendes oder vorheriges Ereignis. Solange 
die Programmabarbeitung innerhalb einer void nicht stopt oder verzögert 
wird habe ich einen ständigen "Kreislauf". In jeder void kann ich 
fragen: Was kann ich für dich tun? Antwort: Nichts, ok, mal sehen was 
der nächste hat. Genau so kann ich in jeder void auch eine if Abfrage 
einbauen und in Abhängigkeit der Antwort eine andere case (Zahl) 
auswählen. Kann ich auch einen Wert zurückgeben oder in einer globalen 
Variable speichern?
achim

[Falk B. (falk)]

@ Achim Seeger (achims)

Hallo Achim, was macht der Niobee?

>Die Beispiel (einfach) die ich bisher gefunden und verwendet habe laufen
>fast immer nach dem gleichen Schema (vereinfacht)

Ja.

>Dabei wird durch den Aufruf der task immer wieder die void aufgerufen.

Was bitte? Ein void aufgerufen? Weisst du, was void auf deutsch heißt? 
Nichts, leer.

>Innerhalb der void können die verschiedenen Teile ausgeführt werden.

Nö, das ist ein vollkommen voider Satz. ;-) Void ist der Datentyp des 
Rückgabeparameters, in diesem Fall gibt es also keinen 
Rückgabeparameter. Das muss aber nicht so sein.

>Aufruf von task immer en nachfolgendes oder vorheriges Ereignis. Solange
>die Programmabarbeitung innerhalb einer void

Hör auf mit solchen abstrusen Formulieruingen. Das ist eine ganz normale 
C-Funktion. Punkt.

> nicht stopt oder verzögert
>wird habe ich einen ständigen "Kreislauf".

Ja.

>auswählen. Kann ich auch einen Wert zurückgeben oder in einer globalen
>Variable speichern?

Natürlich, er will dich daran hindern?

[Maxx (Gast)]

Das Beispiel ist dabei jedoch keine Software-Nachbildung eines endlichen 
Automaten (State Machine)

Diese besteht aus einer Menge an Zuständen (konstant), dem aktuellen 
Zustand(daten) und einer Menge von programmatisch erfassten 
Übergängen(code) von einem zugewiesenen Zustand (Wert des Datums) in 
einen anderen (Wert des Datums) bei einer Eingabe/Ereignis.



Neben den Nachbildungen eines endlichen Automaten in Software ist jedoch 
immer das gesamte System, egal was du damit machst, bereits ein 
endlicher Automat. Die Frage also wie du einen endlichen Automaten 
erkennst: Läuft es auf dem Mikrocontroller, dann ist es einer:
Hier ist der aktuelle Zustand die Menge aller veränderlichen 
Speicherstellen in ihrer aktuellen Ausprägung, die Übergänge sind die 
Maschinenbefehle und die Menge aller Zustände sind alle Kombinationen 
die die gesamtheit der veränderlichen Speicherstellen einnehmen kann.

[Kindergärtner (Gast)]

Achim Seeger schrieb:
> die void
Achim Seeger schrieb:
> innerhalb einer void nicht
Was ist denn "eine void"?! "void" in C ist ein Datentyp für "gar 
nichts", den man bei Funktionen ohne Rückgabetyp angibt.

int main () {
  int a,b;
  while (1) {
    scanf ("%c",&a);
    if (a == 'q') break;
    scanf ("%c", &b);
    if (b == 'x') printf ("bla1\n");
    if (b == 'y' && a == 'x') printf ("bla2\n");
  }
}

Das da enthält kein switch-case und keine Funktionen und ist trotzdem 
eine State Machine. Der aktuelle Zustand wird implizit über die Stelle 
(Zeile), die der Prozessor gerade ausführt sowie die Inhalte der 
Variablen a,b gespeichert; es gibt also keine explizite 
Zustands-Variable.

[Martin L. (maveric00)]

Hallo,

ich würde als Kennzeichen einer State-Machine den Zustand sehen - also 
eine oder mehrere (integer) Variable(n), die zwischen den Durchläufen 
des Algorithmus ihren Wert behalten (also "statisch" sind), und die 
durch den Algorithmus modifiziert werden können. Ein weiteres Kriterium 
ist, dass der Ablauf des Algorithmus von der/den Variable(n) abhängt. 
Letzteres kann aber durchaus trickreich versteckt sein (z.B. bei 
boolschen Berechnungen).

Ob dies durch eine If-Then-Else, durch boolsche (oder andere) 
Berechnungen, innerhalb einer switch-case oder wie auch immer passiert, 
ist nebensächlich (auch wenn klassisch bei einer Umsetzung einer 
State-Machine gerne eine switch-case-Kette mit der Zustandsvariablen im 
switch verwendet wird).

Dein letztes Posting ist ein bischen wirr zum Schluss - void ist nur die 
Definition des Rückgabewertes der Funktion mit der Bedeutung "Kein 
Rückgabewert". Wenn die Funktion keine globalen Variablen beschreibt und 
auch sonst nebenwirkungsfrei wäre (also keine Ausgaben tätigt und keine 
Hardware anspricht) könnte man sie auch komplett einsparen, da sie bis 
auf Prozessorzeitverbrauch nichts bewirkt.

Um aus Deinem Beispiel eine State-Machine zu machen, müsste Task 2 etwa 
so aussehen

void task 2
{
static int Zahl ;

switch (Zahl)
case 1:
tu was (mit Nebenwirkungen)
Modifiziere ggf. Zahl
break ;
case 2:
was anderes (mit Nebenwirkungen)
Modifiziere ggf. Zahl
break ;
}

Ich nehme an, dass sich das while(1) sowohl auf Task 1 als auch auf Task 
2 bezieht. Dadurch wird die State-Machine immer wieder aufgerufen und 
kann funktionieren. Dies ist Sinnvoll, wenn innerhalb der States 
bestimmte Algorithmen regelmäßig (hier: ständig) ausgeführt werden 
sollen. Alternativ zum while(1) kann auch Task 2 wirklich als Task in 
einem Scheduler ausgeführt werden, wodurch die Algorithmen in 
regelmäßigen Zeitabständen ausgeführt würden

Eine andere Methode ist, die State-Machine nur dann aufzurufen, wenn ein 
Ereigniss eintritt, welches eine Zustandsänderung hervorrufen könnte. 
Dies funktioniert jedoch nur für State-Machines, die nur bei 
Zustandsänderung eine Aktion auslösen. Task 2 würde dann so aussehen:

void task 2
{
static int Zahl ;

switch (Zahl)
case 1:
if (Change State to 2) {
Löse Aktion StateChange 1->2 aus (mit Nebenwirkungen)
Zahl = 2 ;
}
break ;
case 2:
if (Change State to 1) {
Löse Aktion StateChange 2->1 aus (mit Nebenwirkungen)
Zahl = 1 ;
}
break ;
}

State-Machines sind immer dann gut nutzbar, wenn man eine definierte 
Anzahl von Zuständen und Zustandsübergänge hat, für die bestimmte 
Algorithmen ausgeführt werden sollen (z.B. Kaffeemaschine oder 
Lichtschalter oder aber auch eine Ampel). Dementsprechend eignen sie 
sich auch gut zur Benutzerführung (z.B. Geldautomat: Warten auf Karte -> 
Warten auf Pin -> Eingabe Auszahlungsbetrag -> Validieren Bonität -> 
Auszahlung -> Rückgabe Karte -> Start, mit einem Abbruch-Knopf, der ggf. 
immer in den Zustand "Rückgabe Karte" überführt). Man muss nur 
aufpassen, dass man nicht versucht, alle Probleme mit einer 
State-Machine zu erschlagen...

Schöne Grüße,
Martin

[Achim S. (achims)]

Hallo Falk
Danke der Nachfrage. Nach einer Sommerpause, versuche ich wieder die 
Technik und das programmieren zu begreiffen. Je weiter ich komme, um so 
mehr begreiffe ich das ich nichts weiss (Philosophie???)
Arbeite dopch schon längere Zeit an Multitasking. Nach dem ich das 
andere begriffe (hoffentlch) habe kommt das nächste Thema - State 
Maschine. Mit dem anderen Thema habe ich schon einiges an Diskussion 
ausgelöst. Zu deinen Antworten:

>Dabei wird durch den Aufruf der task immer wieder die void aufgerufen.

Was bitte? Ein void aufgerufen? Weisst du, was void auf deutsch heißt?
Nichts, leer.

Ich verwende void als unterfunktion (Bitte um entschuldigung, falls 
falsch ausgedrückt) z.B. (vereinfachet Darstellung)

void Nibo2 ()
{  (Programm)  }

das kann ich beliebig aufrufen und Parameter übergeben z.B. mit

while (1)
{
nibo2 ();
}
return

Innerhalb dieser Funktin kannich doch verschiede Sachen ausführen, z.B. 
Display löschen, Ausgabe Schrift usw.

Wenn ich mehrere void verwende z.B. Nibo 1, Nibo 2, Nibo 3 usw. kann ich 
in der void entsprechende switch/case sachen ausführen und kann einen 
Wert zurückgeben und weiter in die nächsten laden und verarbeiten. Das 
kann ich alles in C machen. Innerhalb der void kann ich verschiedene if 
Abfragen haben und daurch auch verschiedene Rückgabewerte erhalten. Sehe 
ich das falsch?
achim

[Martin L. (maveric00)]

Hallo,

Kindergärtner schrieb:
> Das da enthält kein switch-case und keine Funktionen und ist trotzdem
> eine State Machine. Der aktuelle Zustand wird implizit über die Stelle
> (Zeile), die der Prozessor gerade ausführt sowie die Inhalte der
> Variablen a,b gespeichert; es gibt also keine explizite
> Zustands-Variable.

Sehe ich anders - ich denke Du verwechselst hier den Prozessor als 
Zustandsautomat mit der Klassifikation des Algorithmus als 
State-Machine. Mit der Argumentation wäre nämlich jedes (nicht linear 
ablaufende) Programm eine State-Machine. Dadurch, dass a und b jedoch in 
jedem Durchlauf zwangsweise von aussen neu besetzt werden, gibt es noch 
nicht einmal eine implizite Zustandsvariable und damit auch keinen 
Zustand des Algorithmus.

Schöne Grüße,
Martin

[Achim S. (achims)]

Hallo
können wir uns soweit einigen das man eine State Maschine unter anderem 
mit einer

switch (Zahl)
case (Zahl)
tuwas
break
case (Zahl)
was anderes
brek

usw

ausführen kann. Dabei ist auch eine anderee Aufbau z.B. mit

int main () {
  int a,b;
  while (1) {
    scanf ("%c",&a);
    if (a == 'q') break;
    scanf ("%c", &b);
    if (b == 'x') printf ("bla1\n");
    if (b == 'y' && a == 'x') printf ("bla2\n");
  }
}

möglich und auch andere. Möche zum Anfang aber dabei bleiben, um es zu 
verstehen und nicht zu komplziert machen
achim

[Kindergärtner (Gast)]

Achim Seeger schrieb:
> Ich verwende void als unterfunktion (Bitte um entschuldigung, falls
> falsch ausgedrückt)
Das ist völlig verkehrt ausgedrückt. Das was du als "void" verstehst ist 
einfach nur eine Funktion. Eine Funktion kann man aufrufen, eine 
Funktion kann dinge tun, eine Funktion kann etwas zurückgeben. Und wenn 
man eine Funktion deklarieren will, die nichts zurückgibt, schriebt man 
"void" daran - aber deswegen ist es immer noch eine Funktion und keine 
"void". Man könnte sie höchstens "Prozedur" nennen, wie es die 
Pascal-Leute tun.

Martin L. schrieb:
> Sehe ich anders - ich denke Du verwechselst hier den Prozessor als
> Zustandsautomat
Der prozessor+speicher hat nur endlich viele Zustände (2^anzahl 
flipflops), ist also ein Zustandsautomat.
> mit der Klassifikation des Algorithmus als
> State-Machine.
Jeder Algorithmus, der mit endlichem Zustand rechnet, ist eine State 
Machine.
> Mit der Argumentation wäre nämlich jedes (nicht linear
> ablaufende) Programm eine State-Machine.
Ist es ja auch; Da "reale" Integer und sonstige Datentypen (inkl. 
Pointer) nur endlich viele Zustände annehmen können, Programme nur 
endlich lang sein können sind alle realen Programme endliche Automaten = 
Finite State Machines.
> Dadurch, dass a und b jedoch in
> jedem Durchlauf zwangsweise von aussen neu besetzt werden, gibt es noch
> nicht einmal eine implizite Zustandsvariable und damit auch keinen
> Zustand des Algorithmus.
Nein, in allen Zeilen bis auf denen mit scanf() werden die Variablen 
beibehalten, also gibt es einen Zustand. In der Zeile mit dem letzten 
if() wird zB für verschiedene Werte von a unterschieden; also 
verschiedene Zustände. Und je nachdem in welcher Zeile man ist, hat man 
auch einen anderen Zustand.

[Kindergärtner (Gast)]

PS: Man kann jedes "reale" Programm in einen Zustandsgraphen überführen, 
indem man für jede Programmzeile (streng genommen: jede 
Maschineninstruktion) und jede mögliche Variablenbelegung einen Zustand 
anlegt und entsprechende Übergänge einbaut. Das wird zwar schnell 
ziemlich unübersichtlich & unoffensichtlich (kein direkt 
offensichtlicher Zusammenhang zum Sourcecode, wie es zB bei o.g. 
switch-case-Konstrukten ist), beweist aber dass alle Programme State 
Machines sind.

[Falk B. (falk)]

@ Achim Seeger (achims)

>Was bitte? Ein void aufgerufen? Weisst du, was void auf deutsch heißt?
>Nichts, leer.

>Ich verwende void als unterfunktion (Bitte um entschuldigung, falls
>falsch ausgedrückt) z.B. (vereinfachet Darstellung)

Deine Zitate sind falsch markiert und damit schwer lesbar.

http://www.afaik.de/usenet/faq/zitieren/

>void Nibo2 ()
>{  (Programm)  }

>das kann ich beliebig aufrufen und Parameter übergeben z.B. mit

>while (1)
>{
>nibo2 ();
>}

Ja sicher.

>return

>Innerhalb dieser Funktin kannich doch verschiede Sachen ausführen, z.B.
>Display löschen, Ausgabe Schrift usw.

Ja.

>Wenn ich mehrere void verwende z.B. Nibo 1, Nibo 2, Nibo 3 usw.

NEIN! Du schreibst jetzt 100 mal.

"Es gibt keine void. Das heißt Funktion ohne Rückgabeparameter."


> kann ich
>in der void

AHHHH!! Hört auf mit dieser Babysprache!

>entsprechende switch/case sachen ausführen und kann einen
>Wert zurückgeben und weiter in die nächsten laden und verarbeiten. Das
>kann ich alles in C machen. Innerhalb der void kann ich verschiedene if
>Abfragen haben und daurch auch verschiedene Rückgabewerte erhalten.

Ja, das kann man. Ein ganz normales Verhalten einer Funktion. Wenn das 
Ergebnis (Rückgabewert) immer gleich wäre, wäre die Funktion sinnlos.

[Fabian O. (xfr)]

Bei einer Statemachine gibt es eine Variable, die dauerhaft einen 
Zustand speichert. Je nach Zustand (= Wert der Variable) macht die 
Maschine etwas anderes. Sie kann ihren Zustand selbstständig wechseln, 
etwa in Abhängigkeit von Eingabewerten oder anderen Bedingungen.

Im Programmcode sieht man das oft in einer Funktion, die je nach Wert 
einer globalen bzw. statischen Variable etwas anderes tut. Um das 
umzusetzen, nimmt man oft ein switch-case-Konstrukt. Es geht aber 
natürlich genauso mit if/else oder wie schon erwähnt "versteckt" in 
einer Berechnung.

Achim Seeger schrieb:
> switch (Zahl)
> case (Zahl)
> tuwas
> break
> case (Zahl)
> was anderes
> brek

In diesem Fall wäre "Zahl" die Zustandsvariable. Sie muss außerhalb der 
Funktion (global) bzw. innerhalb der Funktion als "static" definiert 
werden, damit sie ihren Wert auch nach Verlassen der Funktion behält. 
Innerhalb eines case darf "Zahl" auch verändert werden. Dann macht die 
Funktion bei ihrem nächsten Aufruf etwas anderes. Beispiel:

int zustand = 0;

void meine_funktion(void)
{
  switch (zustand) {
    case 0:
      printf("A");
      zustand = 1;
      break;
    case 1:
      printf("B");
      zustand = 2;
      break;
    case 2:
      printf("C");
      zustand = 0;
      break;
  }
}

Diese Funktion gibt beim ersten Aufruf "A" aus. Wenn man sie nochmal 
aufruft, gibt sie "B" aus. Beim nächsten Aufruf "C". Und beim nächsten 
Aufruf wieder "A". Wenn man sie in einer Endlosschleife aufrufen würde 
also "ABCABCABCABC...".

Wann welche Aktion ausgeführt wird und ob und in welchen neuen Zustand 
gewechselt wird, kann natürlich beliebig komplex sein. Es könnte z.B. 
auch von Benutzereingaben abhängen oder davon, ob eine bestimmte Zeit 
abgelaufen ist. Bei der Mikrocontrollerprogrammierung kann man diese 
Prinzip benutzen, um Multitasking zu realisieren, wie Du ja schon 
erkannt hast.

Noch etwas zur Umsetzung: Damit man besser erkennt, was die Zustände 
bedeuten, sollte man ihnen Namen geben und nicht nur mit Zahlen im Code 
("Magic Numbers") arbeiten. Außerdem wäre es in diesem Fall geschickter, 
die Zustandsvariable nicht global sondern innerhalb der Funktion als 
"static" zu definieren. Dann wird sie nur einmalig bei Programmstart 
initialisiert und behält daraufhin immer den zuletzt zugewiesenen Wert, 
auch über den Aufruf der Funktion hinaus. Das ist als Anfänger eventuell 
etwas verwirrend. Dieses Beispiel macht das gleiche wie das obige:

#define PRINT_A 0
#define PRINT_B 1
#define PRINT_C 2

void meine_funktion(void)
{
  static int zustand = PRINT_A;
  switch (zustand) {
    case PRINT_A:
      printf("A");
      zustand = PRINT_B;
      break;
    case PRINT_B:
      printf("B");
      zustand = PRINT_C;
      break;
    case PRINT_C:
      printf("C");
      zustand = PRINT_A;
      break;
  }
}

Mit der Zuweisung eines Werts an die Variable "zustand" legt man also 
fest, was beim nächsten Aufruf der Funktion passieren soll. Das ist 
letztlich die Kernidee, wenn man eine Statemachine in einem 
Mikrocontrollerprogramm verwendet: Man speichert in einer (oder 
mehreren) Variable(n), was beim nächsten Mal zu tun ist. In der 
Zwischenzeit kann man sich um andere Dinge kümmern.

[Martin L. (maveric00)]

Hallo,

Kindergärtner schrieb:
> PS: Man kann jedes "reale" Programm in einen Zustandsgraphen überführen,
> indem man für jede Programmzeile (streng genommen: jede
> Maschineninstruktion) und jede mögliche Variablenbelegung einen Zustand
> anlegt und entsprechende Übergänge einbaut.

das war an sich dass, was ich mit der Differenzierung des Prozessors als 
Zustandsautomat und dem Algorithmus als State-Machine ausdrücken wollte:

Natürlich kann die reale Umsetzung eines Algorithmus in ein 
Computer-Programm immer durch ein Zustandsdiagramm dargestellt werden; 
zumindest wenn der Algorithmus aber auch auf einem Analog-Rechner ohne 
Relais o.ä. darstellbar ist, würde ich (und vermutlich viele andere 
ebenfalls) nicht von einer State-Machine reden.

Und das ist auch bei dem scanf-Beispiel der Fall: Natürlich hat der 
Prozessor und der Speicher verschiedene Zustände, der Algorithmus jedoch 
nicht - die Ausgangsgrößen (Ausgabe) hängen ausschließlich von den 
Eingangsgrößen (Eingabe) und nicht von einer Historie ab. Einzig über 
die Frage, ob das break eine Zustandsmaschine aufbaut (mit genau zwei 
Zuständen: Automat läuft oder läuft nicht) könnte man meiner Meinung 
nach streiten.

Aber ich glaube, wir verwirren den TO damit ein bischen. Genau das 
meinte ich übrigens mit dem Satz "Man muss nur aufpassen, dass man nicht 
versucht, alle Probleme mit einer State-Machine zu erschlagen...", da 
diese dann häufig zu kompliziert und unübersichtlich werden.

An den TO: Ich möchte Dir dringend nahelegen, Dich an die üblichen 
Bezeichner zu gewöhnen und nicht neue zu "erfinden" - sonst wirst Du uns 
und wir Dich nicht verstehen. "die void" bezeichnen alle anderen als 
"die Unterfunktion". Das C die Klassifikation "void" für Unterfunktionen 
kennt, die keinen Rückgabewert haben, bedeutet nicht, dass es nicht noch 
andere Unterfunktionen gibt. Oder willst Du wirklich das Konstrukt der 
Unterfunktion noch einmal komplett aufsplitten in "die int, die float, 
die struct time,...)? Viel Sinnvoller ist es (speziell wenn es mehr als 
eine Unterfunktion gibt), den Namen der Unterfunktion zu verwenden (Task 
1, Task 2, Nibo2,...). Dann weiss man auch gleich, welche der Funktionen 
gemeint ist.

Zur Einführung in State-Machines: Gibt man das Wort "Zustandsmaschine" 
in den Gockel ein, dann bekommt man jedenfalls eine große Auswahl von 
Versuchen, das Thema und die Umsetzung in Programme verschiedener 
Sprachen zu erklären.

Schöne Grüße,
Martin

[Reinhard Kern (Gast)]

Achim Seeger schrieb:
> Gibt es klassische Merkmale für eine Statemaschine bzw um sie zu
> erkennen und die Funktion nach vollziehen zu können?

Nicht wirklich. Man kann sich vor dem Codieren eine Zustandstabelle 
definieren, aber ein ordentlicher Programmierer fasst das an einer 
Stelle mit case usw. oder mit einer Sprungtabelle in Assembler zusammen, 
da gibt es viele Möglichkeiten, ein Chaot dagegen verteilt die Abfragen 
in wildem Spaghetti-Code, aber es bleibt eine State machine, man sieht 
es bloss nicht mehr. Ich schreibe allerdings am Anfang des Sourcecodes 
bzw. da wo der Automat programmiert ist i.A. eine Tabelle mit der 
Beschreibung der Zustände und Reaktionen rein, schon für mich selber, 
damit ich die Routinen nacheinander programmieren und abhaken kann.

Zustandsvariable und Verzweigungen sind kein brauchbares Kennzeichen, 
die gibt es in fast jedem real exisierenden Programm.

Tut mir leid, aber so einfach lässt sich Software nicht kategorisieren, 
für eine bestimmte Aufgabe kann man nahezu unendlich viele Programme 
schreiben, gute und schlechte, aber selbst das ist nicht so leicht zu 
unterscheiden.

Gruss Reinhard

[Kindergärtner (Gast)]

Martin L. schrieb:
> zumindest wenn der Algorithmus aber auch auf einem Analog-Rechner ohne
> Relais o.ä. darstellbar ist, würde ich (und vermutlich viele andere
> ebenfalls) nicht von einer State-Machine reden.
Ich würd eher sagen, wenn der Algo nur auf einem Analog-Rechner 
ausführbar ist (aber nicht einem digitalrechner), könnte es eventuell 
keine Statemachine mehr sein. Denn schließlich kann man jeden 
Digital-Rechner-Algorithmus auch genausogut auf einem Analogrechner 
ausführen, indem man eben von den unendlich vielen möglichen 
Spannungspegeln nur 2 auswählt.
Wenn er auch auf einem Digitalrechner läuft, kommt er scheinbar auch mit 
endlich vielen Zuständen aus, ist also als Finite State Machine 
ausdrückbar.

Martin L. schrieb:
> Und das ist auch bei dem scanf-Beispiel der Fall: Natürlich hat der
> Prozessor und der Speicher verschiedene Zustände, der Algorithmus jedoch
> nicht
Doch, der Algorithmus kann in den Zuständen "vor dem ersten scanf", 
"nach dem ersten scanf und a=0", "nach dem ersten scanf und a=1", "nach 
dem ersten scanf und a=2", ... "nach dem zweiten scanf und a=0, b=0", 
"nach dem zweiten scanf und a=0, b=1", ... "nach dem zweiten scanf und 
a=255, b=255", "nach dem ersten if(),vor dem 1. printf","nach dem 1. 
printf", etc. sein. Die Übergänge werden jeweils durch den Takt des 
Prozessors angestoßen, nur die scanf-Übergänge enthalten eine Schleife 
(libc-intern) die eben auf eine Eingabe wartet und erst danach das 
äußere Programm weiterlaufen lässt.

Martin L. schrieb:
> Aber ich glaube, wir verwirren den TO damit ein bischen.
Das kann sein. Aber das ist ein interessantes Thema, denn mir scheint 
man könnte viele State Machines einfacher durch ordinäre C-Algorithmen 
ausdrücken, anstelle der strengen Schreibweise mit einer einzigen 
Zustandsvariablen und einem switch-case-monstrum.

[Achim S. (achims)]

Hallo Martin, Hallo Fabian
danke für eure Hilfe. sehe wo mein denkfehler liegt. Eigentlich hatte 
ich es richtig verstanden, da aber viele Erklärungen im netz stehen und 
nicht alle so verständlich sind kommt es schon zu Problemen.

Fabian O. schrieb:
> #define PRINT_A 0
> #define PRINT_B 1
> #define PRINT_C 2
>
> void meine_funktion(void)
> {
>   static int zustand = PRINT_A;
>   switch (zustand) {
>     case PRINT_A:
>       printf("A");
>       zustand = PRINT_B;
>       break;
>     case PRINT_B:
>       printf("B");
>       zustand = PRINT_C;
>       break;
>     case PRINT_C:
>       printf("C");
>       zustand = PRINT_A;
>       break;
>   }
> }

Fabian O. schrieb:
> Mit der Zuweisung eines Werts an die Variable "zustand" legt man also
> fest, was beim nächsten Aufruf der Funktion passieren soll. Das ist
> letztlich die Kernidee, wenn man eine Statemachine in einem
> Mikrocontrollerprogramm verwendet: Man speichert in einer (oder
> mehreren) Variable(n), was beim nächsten Mal zu tun ist. In der
> Zwischenzeit kann man sich um andere Dinge kümmern.

In deinem letzten Teil steht es allgemein verständlich drin. Damit kann 
ich es nachvollziehen. Sehr gute Erklärung. Die Erstelllung eines 
ablaufes und die Umsetzung in ein Programm ist was anderes (erst mal für 
mich). Da hilft nur machen und aus fehlern lernen. Danke
achim

[Martin L. (maveric00)]

Hallo,

ich glaube, wir haben leicht unterschiedliche Ansichten, wie weit man 
den Begriff "State-Machine" im Bezug auf Algorithmen (und nicht deren 
praktische Umsetzung) anwenden sollte - macht aber nichts ;-)

Kindergärtner schrieb:
> Das kann sein. Aber das ist ein interessantes Thema, denn mir scheint
> man könnte viele State Machines einfacher durch ordinäre C-Algorithmen
> ausdrücken, anstelle der strengen Schreibweise mit einer einzigen
> Zustandsvariablen und einem switch-case-monstrum.

Das ist sicher in vielen Fällen möglich, wo eine formale State-Machine 
aufgebaut wurde, wo es auch ein paar Fallunterscheidungen getan hätten 
(womit ich wieder bei "Man muss nur aufpassen..." wäre). Ist halt oft 
so, dass man versucht, das aktuelle Problem mit der Methode zu 
erschlagen, die man für das letzte Problem erfolgreich angewendet oder 
gelernt hat.

Interessanter wird es, wenn es einem gelingt, den diskreten Ablauf durch 
einen kontinuierlichen Ablauf zu ersetzen. Dabei können erhebliche 
Vereinfachungen entstehen, speziell was die Übergänge zwischen den 
einzelnen "Zuständen" angeht (Stichwort "Change of Mind"). Ein Ansatz 
dazu ist ja auch die Fuzzy-Logik, andere Ansätze ergeben sich je nach 
Anwendungsgebiet des Algorithmus (z.B. Regelung von Maschinen etc.).

Schöne Grüße,
Martin