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.
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
public class Nea<A, S> extends HashMap<Pair<A, S>, Set<S>> {
Set<S> starts;
Set<S> ends;
Set<A> alphabet;
public Nea(Set<S> starts, Set<S> ends, Set<A> alphabet) {
this.starts = starts;
this.ends = ends;
this.alphabet = alphabet;
}
Set<Set<S>> reachableStates() {
Set<Set<S>> result = new HashSet<>();
reachableStates(starts, result);
return result;
}
Set<Set<S>> reachableStates(Set<S> sts, Set<Set<S>> result) {
result.add(sts);
//TODO. calculate all reachable States from a state in sts
return result;
}
public static Nea<Integer,String> example() {
String s0 = "s0";
String s1 = "s1";
String s2 = "s2";
String s3 = "s3";
Set<String> s01 = Set.of("s0", "s1");
Nea<Integer, String> ex = new Nea<Integer, String>(Set.of(s0), Set.of(s3), Set.of(0, 1));
ex.put(new Pair<>(0, s0), s01);
ex.put(new Pair<>(1, s0), Set.of(s0));
ex.put(new Pair<>(0, s1), Set.of(s2));
ex.put(new Pair<>(1, s1), Set.of(s2));
ex.put(new Pair<>(0, s2), Set.of(s3));
ex.put(new Pair<>(1, s2), Set.of(s3));
return ex;
}
}
Subato
