Unter einer FSM versteht man ein in sich geschlossenes System, welches durch eine Menge von Zuständen und deren Übergänge definiert wird. Die Impulse für einen Übergang können von Ausserhalb des Systems kommen oder auch spontan auftreten (dazu später mehr).

Ein Beispiel: An einer gefährlichen Hauptstrasse gibt es einen Fussgängerstreifen, an dem zwei Ampeln installiert sind. Diese beiden Ampeln sind miteinander gekoppelt und sollten (logischerweise) einen sicheren Ablauf des Verkehrs garantieren. Die Fussgänger werden korrekterweise auf einen Knopf B drücken, um der Ampel mitzuteilen, dass sie grünes Licht benötigen, um sicher über die Strasse zu gelangen. Ferner wird gesagt, dass die Ampel für die Autos die drei Farben grün, gelb und rot, die Ampel für die Fussgänger aber nur grün und rot besitzt. Die Aufgabe besteht nun darin, eine FSM für dieses heikle System zu entwerfen, damit keine Umfälle passieren können.

Als ersten Schritt überlegt man sich, welche Zustände benötigt werden, und welche wenn immer möglich nicht auftreten sollten:

Auto	Fussgänger	Situation
GRÜN (G)	grün (g)	Kollisionsgefahr
GRÜN (G)	rot (r)	Autos fahren gefahrlos
GELB (Y)	grün (g)	Kollisionsgefahr, falls Autos vorher oder nachher GRÜN (Fussgänger sind nicht auf einen Schlag weg von der Strasse)
GELB (Y)	rot (r)	Autos halten an oder bereiten sich auf Start vor (gefahrlos)
ROT (R)	grün (g)	Fussgänger haben freie Bahn (gefahrlos)
ROT (R)	rot (r)	Nichts tut sich (gefahrlos, aber wenig sinnvoll)

Man sieht also, dass nur drei Zustände sinnvoll sind. Nun wird zusätzlich noch vorgegeben, dass das System einen Timer eingebaut hat, der nur alle 10 Sekunden das Signal für einen Zustandswechsel gibt. Der Impuls setzt sich also zusammen aus dem Timer und dem eigentlichen Signal: dem Knopf B. Das Signal ist entweder 0 (nicht gedrückt) oder 1 (gedrückt).

Folgendermassen sieht nun eine einfache Lösung des Problems aus:

                        0,1
         +-------------------------------+
         |                               |
         V                               |
  /----#====#    1    #====#    0,1    #====#
0 |    | Gr |-------->| Yr |---------->| Rg |
  \--->#====#         #====#           #====#

Befindet sich beispielsweise das System im Zustand ganz links, so haben die Autofahrer GRÜN und die Fussgänger rot. Solange B nicht gedrückt wird, bleibt das System in diesem Zustand. Sobald jedoch der Knopf gedrückt wird, wechselt die Maschine in den mittleren Zustand: Die Autos sehen GELB und halten an, währen die Fussgänger immer noch rot sehen. Dann (nach 10 Sekunden) wechselt das System bereits wieder in den nächsten Zustand (ob nun B gedrückt ist, oder nicht) und zeigt für die Fussgänger grün und für die Autofahrer ROT. Nach weiteren 10 Sekunden wechselt das System wieder in den Anfangszustand.

Natürlich wäre es nun noch schön, wenn nach dem Rg-Signal zuerst nochmals ein Yr-Signal erscheinen würde, damit die letzten Fussgänger die Strasse noch fertig überqueren und die Autofahrer sich vorbereiten können. Dummerweise gibt es da jedoch ein Problem:

                 0,1              0,1
  /----#====#<---------#====#<----------#====#
0 |    | Gr |          | Yr |           | Rg |
  \--->#====#--------->#====#---------->#====#
                 1                0,1

Wenn sich nun die Maschine im Zustand Yr befindet, welchen Weg soll sie im nächsten Schritt dann nehmen, den nach Gr oder den nach Rg? Die Mashine hat keine Möglichkeit, herauszufinden, welche Richtung gewünscht ist, sie wird deshalb einfach einen auswählen (welcher dann aufgrund der allgemeinen Verwirrung wieder zu Kollisionsgefahr führen kann. In solchen Fällen hilft nur Handzeichen). Diese Art von FSM nennt man nicht-deterministisch (wird später behandelt). Die Lösung dieses Problemes (also eine deterministische FSM) liegt jedoch auf der Hand: Man definiert einfach noch einen zusätzlichen Zustand:

              0,1     #====#      0,1
         +------------| Yr |<------------+
         |            #====#             |
         V                               |
  /----#====#    1    #====#    0,1    #====#
0 |    | Gr |-------->| Yr |---------->| Rg |
  \--->#====#         #====#           #====#

Somit wäre das Prinzip der FSM schon fast erklärt. Was noch dazukommt, ist ein Startzustand: Normalerweise wird mit einem einfachen Pfeil derjenige Zustand markiert, in dem die Maschine startet (oben beispielsweise der Zustand Gr). Hier auf diesen Seiten wird der Startzustand jeweils beschrieben sein. Mit diesen einfachen Angaben kann grundsätzlich alles Programmiert werden, was man will. Natürlich ist dies um einiges umständlicher, als in einer Programmiersprache einfach die gewünschte Funktionen aufzurufen, tatsächlich könnten diese Funktionen jedoch wie Module betrachtet und in FSM umgeschrieben werden (wenn man das will).

Im folgenden sind hier noch einige Beispiele von einfachen FSM aufgeführt:

Switches:

on-off-toggle-switch (Ein-Aus-Schalter)

Dieser Schalter wechselt zwischen zwei Zuständen hin und her. Nur wenn der Schalter gedrückt wird (1), wird der Zustand gewechselt. Start ist normalerweise bei off.

                  1
  /----#=====#<---------#====#<---\
0 |    | off |          | on |    | 0
  \--->#=====#--------->#====#----/
                  1

set-reset-switch (Setzen-Löschen)

Dieser Schalter wechselt zwischen zwei Zuständen 1 und 0. Beim Signal set wird stets auf 1 gesprungen, bei reset auf 0. Start ist normalerweise bei 0.

                  reset
      /----#===#<---------#===#<---\
reset |    | 0 |          | 1 |    | set
      \--->#===#--------->#===#----/
                   set

3-Bit-Shift-Register

Diese FSM speichert aus einem ständigen Bitstrom die jeweils 3 letzten Bits. Jedes neue Bit wird links in den gespeicherten Status "eingefügt" und das rechteste fällt heraus. Start ist normalerweise bei 000.

               #=====#-------------------------->#=====#
         +---->| 100 |             1             | 110 |-----+
       1 |     #=====#                       /-->#=====#     | 1
         |       ^   \ 0           1        / 1      |       V
  /-->#=====#    |    \-->#=====#---->#=====#        |    #=====#---\
0 |   | 000 |    |1       | 010 |     | 101 |       0|    | 111 |   | 1
  \---#=====#    |        #=====#<----#=====#<--\    |    #=====#<--/
         ^       |      0 /        0           1 \   V       |
       0 |     #=====#<--/                       #=====#     | 0
         +-----| 001 |             0             | 011 |<----+
               #=====#<--------------------------#=====#

Einfacher Modulo-n-Zähler

Diese FSM addiert mit jedem Tick des Taktgebers 1 zum aktuellen Status dazu. Start ist bei Status 0. Nach dem Status n-1 kommt wiederum der Status 0. Zusätzlich gibt es noch ein Eingangssignal reset, welches den Zähler von jedem Zustand aus wieder auf 0 setzt.

  /------------------------------------------------\
  |                                                |
  \->#===#     #===#     #===#            #=====#  |
     | 0 |---->| 1 |---->| 2 | . . . ---->| n-1 |--/
  /->#===#     #===#     #===#            #=====#
  |             /         /                /
  \------------/---------/----------------/
                     reset

Bit-Addierer

Diese FSM Addiert jeweils zwei Bits und speichert das Carry als einen der beiden Zustände ab. Für die Addition einer 32-Bit-Zahl beispielsweise werden einfach alle Bit-Paare der beiden zu addierenden Zahlen nacheinander (LSB first) eingegeben. Zur Schreibweise: Die beiden Eingabe-Bits stehen links des / und rechts davon das, was das Ergebnis der aktuellen 2-bit-Rechnung war (Dies wird ebenfalls später noch genauer behandelt).

              10/1                 01/0
             /---\                /---\
             |   V      11/0      V   |
     /--->#=========#--------->#=========#----\
00/0 |    | carry 0 |          | carry 1 |    | 11/1
     \----#=========#<---------#=========#<---/
             |   ^      00/1      ^   |
             \---/                \---/
              01/1                 10/0

Modulo-3-Dividierer

Diese beiden FSM berechnen, was das Resultat einer Zahl Modulo 3 ergibt. Im ersteren Fall wird die zu berechnende Zahl MSB-first, im zweiteren Fall LSB-first eingegeben. Gestartet wird im ersteren Fall im Zustand 0, im zweiteren im rechten Zustand 0.

MSB:
  /----#===#<---------#===#<----------#===#<---\
0 |    | 0 |     1    | 1 |     0     | 2 |    | 1
  \--->#===#--------->#===#---------->#===#----/


LSB:
       /-----#===#<------#===#<----\
      / 1    | 0 |   0   | 0 |    1 \
     /   /-->#===#------>#===#---\   \
    V   /                         V   \
    #===#                         #===#
    | 2 |                         | 1 |
    #===#                         #===#
    \   ^                         /   ^
     \   \---#===#<------#===#<--/   /
      \ 0    | 2 |   1   | 1 |    0 /
       \---->#===#------>#===#-----/