Im Kapitel 1.2 wird ein endlicher Automat als ein Computer, der eine Eingabe abarbeitet, betrachtet. In dieser Aufgabe sollen Sie dieses Modell als eine Javaklasse realisieren.
Ein Automat sei generisch über das Alphabet und die Menge der Zustände.
Ein Automat ist eine Abbildung von Alphabet-Zustands-Paaren auf einen Nachfolgezustand.
Es gibt einen festen Anfangszustand und eine Menge von Endzuständen.
Die Eingabe wird durch einen Iterator über das Alphabet dargestellt.
Implementieren Sie die folgenden Methoden:
- boolean step(): Der Automat soll einen Zustandsübergang machen und als Wahrheitswert angeben, ob für das nächste Zeichen der Eingabe und dem aktuellen Zustand eine Überführungsfunktion existierte. Ob also eine Zustandsübergang durchgeführt wurde.
- boolean run(): Sie soll so lange die Methode step aufrufen, bis kein Übergang mehr stattfindet. Dann soll sie zurückgeben, ob alle Zeichen der Eingabe verarbeitet wurden und der Endzustand erreicht wurde.
Als Beispiel ist der erste Automat aus dem Skript formuliert.
public class Pair<A, B> {
private A _e1;
private B _e2;
public Pair(A _e1, B _e2) {
super();
this._e1 = _e1;
this._e2 = _e2;
}
public A e1() {return _e1;}
public B e2() {return _e2;}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((_e1 == null) ? 0 : _e1.hashCode());
result = prime * result + ((_e2 == null) ? 0 : _e2.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair other = (Pair) obj;
if (_e1 == null) {
if (other._e1 != null)
return false;
} else if (!_e1.equals(other._e1))
return false;
if (_e2 == null) {
if (other._e2 != null)
return false;
} else if (!_e2.equals(other._e2))
return false;
return true;
}
@Override
public String toString() {
return "Pair [_e1=" + _e1 + ", _e2=" + _e2 + "]";
}
}
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class Automat<A, S> extends HashMap<Pair<A,S>,S>{
Iterator<A> input;
S state;
S initialState;
Set<S> terminalStates;
public Automat(S initialState, Set<S> terminalStates) {
this.initialState = initialState;
this.terminalStates = terminalStates;
}
void initialize(Iterator<A> input) {
this.input=input;
state=initialState;
}
boolean step(){
//TODO
return false;
}
boolean run() {
//TODO
return false;
}
static Automat<Integer,String> getExample(){
var s0 = "s_0";
var s1 = "s_1";
var s2 = "s_2";
var s3 = "s_3";
var a1 = new Automat<Integer, String>(s0, Set.of(s3));
a1.put(new Pair<>(1, s0), s0);
a1.put(new Pair<>(0, s0), s1);
a1.put(new Pair<>(1, s1), s0);
a1.put(new Pair<>(0, s1), s2);
a1.put(new Pair<>(0, s2), s2);
a1.put(new Pair<>(1, s2), s3);
a1.put(new Pair<>(0, s3), s3);
a1.put(new Pair<>(1, s3), s3);
return a1;
}
}
Subato
