Implementierung eines erkennenden Automaten

Die Umsetzung eines deterministisch endlichen Automaten in ein Programm kann durch eine einziges Objekt einer Klasse erfolgen. Dieser Entwurf wird dem Prinzip der Objektorientierung zwar nicht gerecht, ist aber bei Auomaten, die nicht erweitert werden müssen, schnell und einfach.
Im Gegensatz dazu könnte man auch eine Klasse Zustand entwerfen, bei der Objekte die einzelnen Zustände repräsentieren.
Zunächst soll der erste Weg vorgestellt werden.

Implementierung durch eine Klasse mit nur einem Objekt

Wir betrachten das Beispiel eines Automaten, der Wörter über dem Alphabet {a,b,c}akzeptiert, bei denen zwei 'a' in Folge vorkommen.

Zur Umsetzung wählen wir folgenden Klassenentwurf:

Die Klasse Automat_doppelA verfügt nur über ein Attribut zustand, das den aktuellen Zustand als Zahl speichert. Die Methode boolean untersucheWort(String wort) erwartet als Parameter das zu prüfende Wort und gibt je nachdem, ob das Wort akzeptiert wurde oder nicht, den entsprechenden Wahrheitswert zurück.
Die Methode void wechsleZustand(char zeichen) verändert die Variable zustand je nach momentanem Zustand und Zeichen. Zur Fallunterscheidung eignet sich dabei die switch-Anweisung von Java. Für jedes einzelne Zeichen des zu untersuchenden Wortes ruft die Methode boolean untersucheWort(String wort) diese Methode auf.
Der gesamte Quelltext der Klasse Automat_doppelA:

Automat_doppelA.java
public class Automat_doppelA
{
    private int zustand;
 
    public Automat_doppelA(){
    }
 
    public boolean untersucheWort(String wort){
        zustand=0; //Anfangszustand festlegen
        for (int i=0; i<wort.length();i++){
            wechsleZustand(wort.charAt(i));
        }    
        if (zustand==2) return true;  //Endzustand ist akzeptierter Zustand
        else return false; //Endzustand ist nicht akzeptierter Zustand
    }
 
    private void wechsleZustand(char zeichen)
    {
        //Fallunterscheidung für den momentanen Zustand
        switch (zustand) {            
            case 0: {
                //Fallunterscheidung für das Zeichen im Zustand 0
                switch (zeichen) {
                    case 'a': {zustand = 1;} break; //in den Zustand 1 wechseln
                    case 'b': {zustand = 0;} break; //im Zustand 0 bleiben
                    case 'c': {zustand = 0;} break; //im Zustand 0 bleiben
                }
            }
            break;
 
            case 1: {
                //Fallunterscheidung für das Zeichen im Zustand 1
                switch (zeichen) {
                    case 'a': {zustand = 2;} break; //in den Zustand 2 wechseln
                    case 'b': {zustand = 0;} break; //in den Zustand 0 wechseln
                    case 'c': {zustand = 0;} break; //in den Zustand 0 wechseln
                }
            }
            break;
 
            case 2: {
                //Fallunterscheidung für das Zeichen im Zustand 2
                switch (zeichen) {
                    case 'a': {zustand = 2;} break; //im Zustand 2 bleiben
                    case 'b': {zustand = 2;} break; //im Zustand 2 bleiben
                    case 'c': {zustand = 2;} break; //im Zustand 2 bleiben
                }
            }
            break;
        }
    }    
}

Der Code enthält also zwei geschachtelte switch-Konstruktionen. Da in manchen Zuständen die Eingabe bestimmter Zeichen keine Zustandsänderung bewirkt oder die Eingabe verschiedener Zeichen die gleiche Zuständsänderung bewirkt, kann der Quelltext vereinfacht werden.

Automat_doppelA.java
public class Automat_doppelA_einfach
{
    private int zustand;
 
    public Automat_doppelA_einfach(){
    }
 
    public boolean untersucheWort(String wort){
        zustand=0; //Anfangszustand festlegen
        for (int i=0; i<wort.length();i++){
            wechsleZustand(wort.charAt(i));
        }    
        if (zustand==2) return true;  //Endzustand ist akzeptierter Zustand
        else return false; //Endzustand ist nicht akzeptierter Zustand
    }
 
    private void wechsleZustand(char zeichen)
    {
        //Fallunterscheidung für den momentanen Zustand
        switch (zustand) {            
            case 0: {
                //Fallunterscheidung für das Zeichen im Zustand 0
                switch (zeichen) {
                    case 'a': {zustand = 1;} break; //in den Zustand 1 wechseln                    
                }
            }
            break;
 
            case 1: {
                //Fallunterscheidung für das Zeichen im Zustand 1
                switch (zeichen) {
                    case 'a': {zustand = 2;} break; //in den Zustand 2 wechseln
                    default: {zustand = 0;} break; //in den Zustand 0 wechseln
                }
            }
            break;
 
        }
    }    
}

Zusammenfassung

  • Endliche Automaten können durch eine einzelne Klasse implementiert werden.
  • Ein Attribut speichert den aktuellen Zustand.
  • In zwei ineinander geschachtelten Fallunterscheidungen wird zunächst der aktuelle Zustand unterschieden und ein Zustandswechsel in Abhängigkeit des gelesenen Zeichens durchgeführt.
Cookies helfen bei der Bereitstellung von Inhalten. Durch die Nutzung dieser Seiten erklären Sie sich damit einverstanden, dass Cookies auf Ihrem Rechner gespeichert werden. Weitere Information
Drucken/exportieren