Benjamins Blog

Automaten sind nicht nur in der theoretischen Informatik ein wichtiges Werkzeug im Bereich der formalen Sprachen zur Überprüfung von Sprachzugehörigkeiten. Eine davon abgeleitete Anwendung ist die Mustererkennung in Zeichenketten mithilfe regulärer Ausdrücke. Aber auch viele Protokolle verteilter Systeme (z.B. TCP) greifen das Konzept von Zustandsautomaten auf, um abhängig von verschiedenen internen Zuständen auf Ereignisse differenziert zu reagieren. Natürlich müssen diese Zustandsautomaten bei der Implementierung von Protokollen auch in Software abgebildet werden. In diesem Artikel möchte ich anhand eines einfachen DFAs aufzeigen, wie solche Zustandsautomaten unter Anwendung des State Patterns in Java realisierbar sind.

In diesem Beispiel soll ein DFA konstruiert werden, der aus allen möglichen Zeichenfolgen bestehend aus Einsen und Nullen genau diejenigen akzeptiert, in denen die Teilworte 01 und 10 gleich oft vorkommen. Der nebenstehende Graph verdeutlicht die Funktionsweise des Automaten. Neben dem Startzustand (S) gibt es zwei gültige Endzustände (A,X) mit gleicher Anzahl von Vorkommen, sowie zwei Zustände (B,Y) die keinen gültigen Endzustand darstellen.

Möchte man nun eine solche Konstruktion implementieren, so muss man Zustände, Übergänge und gültige Kombinationen abbilden. Das State Pattern der GoF als Verhaltensmuster bietet sich bei objektorientierten Sprachen an, da es übersichtlicher, sauberer und erweiterbarer ist als Kaskaden von If-Abfragen oder Switch-Statements-Konstrukten. Die Grundidee hierbei ist, Zustände mit zugehörigen Übergängen in eigene Objekte auszulagern und dem zustandsbehafteten Objekt die entsprechende Referenz auf seinen aktuellen Zustand zu übergeben. Änderungen delegiert dieses zustandsbehaftete Objekt dann an sein aktuelles Zustandsobjekt, welches eventuell nach dem Übergang ersetzt wird. In Java bietet es sich an, die Zustände als Enum-Instanzen zu realisieren und diese ein Interface implementieren zu lassen, welches die Übergange definiert. Zusätzlich lassen sich die Zustände, also Enum-Instanzen, darauf hin abfragen, ob sie einen gülitgen finalen Zustand darstellen.
Die Automaton-Klasse stellt nun das eigentliche Objekt dar, was zustandsbehaftet ist, jedoch mit ausgelagerter Behandlung der Zustände:

Transitions.java - Auflistung der Übergänge als Interface

/**
 * Interface listing possible transitions to be implemented by states
 */
public interface Transitions
{
	public void readZero(Automaton a);

	public void readOne(Automaton a);
}

State.java - Zustände als Enum-Typen

/**
 * Enum type for states
 */
public enum State implements Transitions
{
	/**
	 * Initial State - S
	 */
	S
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * Final State - A
	 */
	A
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(B);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * State -B
	 */
	B
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(B);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return false;
		}
	},

	/**
	 * Final State - X
	 */
	X
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(Y);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * State -Y
	 */
	Y
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(Y);
		}

		@Override
		public boolean isFinal()
		{
			return false;
		}
	};

	/**
	 * Is state final?
	 * @return true if final
	 */
	abstract public boolean isFinal();
}

Automaton.java - Das zustandsbehaftete Objekt inklusive Test in der Main-Methode.

/**
 * Automaton class
 */
public class Automaton
{
	//Initial state
	private State state = State.S;

	public void setState(State s)
	{
		this.state = s;
	}

	public void readZero()
	{
		//Delegate...
		state.readZero(this);
	}

	public void readOne()
	{
		//Delegate...
		state.readOne(this);
	}

	public boolean isInFinalState()
	{
		//Delegate...
		return state.isFinal();
	}

	public static void main(String[] args)
	{
		Automaton a = new Automaton();
		String s1 = "11010101";
		for (char c : s1.toCharArray())
		{
			switch (c)
			{
				case '1':
					a.readOne();
					break;
				case '0':
					a.readZero();
					break;
			}
		}
		System.out.println(a.isInFinalState()); //true...
	}
}

Dieses Beispielprogramm mit einem DFA habe ich zum leichteren Verständis gewählt, natürlich lassen sich mit diesem Pattern weit aus komplexere Abläufe modellieren. So könnte der Automat zum Beispiel ein Buch-Objekt einer Bücherei sein und die Übergänge Aktionen wie das Ausleihen, Verlängeren oder Zurückgeben des Buches. Die Zustände als Enum-Typen würden dann auch mehr Geschäftslogik enthalten als das bloße Verändern das Zustands wie hier in diesem Beispiel.