Subato

Resource Files

Minimierung von Automaten

Im Kapitel 1.5 wird ein Algorithmus vorgestellt, mit dessen Hilfe aus einem DEA ein äquivalenter minimierter Automat erzeugt wird. Dieser soll in dieser Aufgabe in Java implementiert werden.

Implementieren Sie die folgende Methode:

  • void unterscheidbareZustaende(Set<Pair<S, S>> u):
    Sie soll den Algorithmus von Seite 19 des Skriptes realisieren. Alle Paare, die aus einem Endzustand und einem Nicht-Endzustand bestehen sind dabei bereits in u enthalten. Der Algorithmus ist also ab Zeile 4 umzusetzen.
  • Set<Set<S>> minimierteZustaende()
    Jetzt, da aus der vorherigen Methode alle Paare von unterscheidbaren Zuständen bekannt sind, lässt sich die Menge alle Äquivalenzklassen von Zuständen berechnen.

Als Beispiel ist der Automat aus dem Skript formuliert.


import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class Automat<A, S> extends HashMap<Pair<A,S>, S>{ S initialState; Set<S> terminalStates; public Automat(S initialState, Set<S> terminalStates) { this.initialState = initialState; this.terminalStates = terminalStates; } Set<S> allStates(){ var rs = new HashSet<S>(); for (var e:this.entrySet()) { rs.add(e.getValue()); rs.add(e.getKey().e2()); } return rs; } Set<A> alphabet(){ var rs = new HashSet<A>(); for (var e:this.entrySet()) rs.add(e.getKey().e1()); return rs; } Set<Pair<S,S>> unterscheidbareZustaende(){ Set<Pair<S,S>> rs = new HashSet<>(); var nonFinal = allStates(); nonFinal.removeAll(terminalStates); for (var s:nonFinal)for(var t:terminalStates) { rs.add(new Pair<>(s, t)); rs.add(new Pair<>(t, s)); } unterscheidbareZustaende(rs); return rs; } void unterscheidbareZustaende(Set<Pair<S, S>> u) { //TODO } Set<Set<S>> minimierteZustaende(){ Set<Set<S>> rs = new HashSet<>(); //TODO return rs; } /** Ein neuer äquivalenter miniminerter Automat auf den Äquivalenzklassen der Zustände wird generiert. **/ Automat<A, Set<S>> minimierterAutomat(){ var zs = minimierteZustaende(); Set<S> startZs = null; Set<Set<S>> finalZs = new HashSet<>(); for (var z:zs) { if (z.contains(initialState))startZs=z; for (var z2:terminalStates)if (z.contains(z2))finalZs.add(z); } var r = new Automat<A, Set<S>>(startZs, finalZs); for (var e:entrySet()) { r.put(new Pair<>(e.getKey().e1() ,zs.stream().filter(z->z.contains(e.getKey().e2())).findAny().get()) ,zs.stream().filter(z->z.contains(e.getValue())).findAny().get()); } return r; } static Automat<Integer,String> getExample(){ var s1 = "s1"; var s2 = "s2"; var s3 = "s3"; var s4 = "s4"; var s5 = "s5"; var s6 = "s6"; var a1 = new Automat<Integer, String>(s1, Set.of(s3,s4,s5,s6)); a1.put(new Pair<>(0, s1), s2); a1.put(new Pair<>(1, s1), s3); a1.put(new Pair<>(0, s2), s2); a1.put(new Pair<>(1, s2), s4); a1.put(new Pair<>(0, s3), s1); a1.put(new Pair<>(1, s3), s5); a1.put(new Pair<>(0, s4), s2); a1.put(new Pair<>(1, s4), s5); a1.put(new Pair<>(0, s5), s2); a1.put(new Pair<>(1, s5), s6); a1.put(new Pair<>(0, s6), s2); a1.put(new Pair<>(1, s6), s1); return a1; } public static void main(String[] args) { System.out.println(getExample().minimierterAutomat()); } }
java
You are not logged in and therefore you cannot submit a solution.