Teilmengen-Konstruktion

Im Kapitel 1.3 wird die Teilmengenkonstruktion vorgestellt, mit deren Hilfe aus einem nichtdeterministischen ein deterministischer endlicher Automat erzeugt wird. Diese soll in dieser Aufgabe in Java implementiert werden.

Ein NEA ist eine Abbildung von Alphabet-Zustands-Paaren auf Mengen von Nachfolgezuständen.

Es gibt eine Menge von Anfangszuständen und eine Menge von Endzuständen.

Das Alphabet der Eingabesprache sei auch gegeben.

Implementieren Sie die folgende Methode:

• Set<Set<S>> reachableStates(Set<S> sts, Set<Set<S>> result):
  Sie soll die Menge aller Teilmenge von Zuständen berechnen, die von einem der Zustände sts erreichbar sind. Hierzu müssen Sie für jedes Zeichen des Alphabets schauen, welche Zustände von einem Zustand in sts erreichbar sind. Wenn die so berechnete Menge noch nicht im result enthalten ist, muss mit dieser die Methode rekursiv aufgerufen werden.

Als Beispiel ist der erste Automat aus dem Skript formuliert.