Revision [10018]

This is an old revision of ZustandsAutomaten made by ToBo on 2009-08-22 00:34:37.

 

Zustandsautomaten


1. Endliche Zustandsautomaten


Einordnung EndlicherAutomat endlicher Zustandsautomaten (engl. Finite State Machines) in der theoretischen Informatik:
image

In der Informatik und der Elektrotechnik werden unterschiedliche Schwerpunkte verfolgt.

In der Elektrotechnik werden endliche Zustandsautomaten (auch Schaltwerke) durch das Zusammenschalten von Logik-Gatter entworfen (vgl. TietzeSchenk2002, S. 699). Heute geschieht das häufiger mit einer Hardware-Beschreibungssprache wie z.B. Vhdl VHDL. Siehe dazu Modellierung von FSMs in VHDL (SkriptSehrVhdl, S. 99)

In der Informatik gibt es neben den endlichen Automaten auch Sonderformen wie Turingmaschinen, Kellerautomaten, nichtdeterministische Automaten etc., die leider meist sehr theoretisch und formal behandelt werden. Hier wird der Student mit Puming-Lemma und Co. behandelt, bis er den Glauben an die Umsetzung in der Praxis verliert. Findet der Informatiker später doch den Bezug zur Realität, so werden vor allem sehr oft die DetEndlAutomaten deterministischen, endlichen Automaten und Kellerautomaten verwendet. Sollen schließlich Automaten vom Informatiker implementiert werden, so werden sie als virtuelle Automaten umgesetzt, die nicht direkt auf der Hardware laufen, sondern als Programm auf der Hardware. Der Automat wird also simuliert. Diese virtuellen Automaten unterscheiden sich deshalb bei genauer Betrachtung von den mit Logik-Gattern umgesetzten Automaten.


2. Virtuelle, endliche Zustandsautomaten


Seit dem Einzug der Computer und Mikrocontroller in der Steuerungstechnik sind nun auch virtuelle, EndlicherAutomat endliche Zustandsautomaten möglich (engl. Virtual Finite State Machines, VFSM). Bei der Umsetzung dieser Art von Zustandsautomaten müssen jedoch einige Randbedingungen im Gegensatz zu realen Zustandsautomaten beachtet werden. Beispielsweise ist hier die Definition von Zustandstabellen empfehlenswert.
http://de.wikipedia.org/wiki/Virtueller_endlicher_Automat
http://www.stateworks.com/active/download/wagf92-software-engineering.pdf


3. Typen


Man kann zwischen einem Mealy-Automaten, einem Moore-Automat und der Kombination aus beiden, den Harel-Automaten, unterscheiden.


3.1Mealy-Automat


Mealy-Automat führt Aktionen im Zustandsübergang aus.

image


3.2Moore-Automat


Moore-Automat führt Aktionen beim Betreten und Verlassen eines Zustands aus.
image


3.3Harel-Automat


Harel-Automat sind Hybride aus Mealy- und Moore-Automaten, sie erlauben zudem bedingte Zustandsübergänge, Zustände mit Gedächtnis, nebenläufige Zustände. Siehe dazu Balzert2000, S. 323 und Zustandsautomaten der SoftwareUml2 UML2.


4. Erweiterte Zustandsautomaten


Erweiterte, endliche Zustandsautomaten besitzen abgesehen von ihren Zuständen, als Erweiterung lokale Variablen, die das Verhalten beim Eintreffen von Ereignissen beeinflussen können, wie bei Zustandsautomaten der SoftwareUml2 UML2 oder allgemein Harel-Automaten.


5. Zustandstabellen


Werden nur bei virtuellen, endlichen Zustandsautomaten benötigt. Eine Zustandstabelle definiert, unter welche Bedingungen von diesem Zustand in einen anderen Führen und was bei Eintritt in den betrachteten Zustand oder beim Verlassen dieses Zustandes ausgeführt wird.


6. State Event Matrix


Die Übergangstabelle (engl. State Event Matrix) bietet eine lückenlose Definition von Übergängen von jedem möglichen Zustand in alle anderen möglichen Zustände in Abhängigkeit von den möglichen Ereignissen. Die Übergangstabelle ist ein effektives Mittel um alle Fälle eines Zustandsautomaten zu erfassen.

Beispiel in Wiegelmann2004, S. 158, allerdings ist der Zustandsautomat dort leider etwas ineffizient mit SWITCH- und CASE-Anweisungen implementiert.


7. Testplan

  • Testplan für Zustandsautomaten
    • Stufe 1: Zustandsabdeckung: Jeder Zustand wird mindestens einmal erreicht.
    • Stufe 2: Abdeckung aller Zustandswechsel: Jeder Zustandsübergang wird mindestens einmal ausgeführt.

Siehe SkcriptRobra2007


8. Relevant

  • ZustandsDiagramm Zustandsdiagramme
  • State invariant
  • defer gibt an, dass ein Event nicht im aktuellen Zustand verarbeitet werden kann, jedoch im nachfolgenden Zustand eine Rolle spielen könnte.



Siehe auch
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki