finite automata example (eugenp#1364)

amihaiemil · pivovarit · commit 19ff2eb487a5 · 2017-03-12T17:15:29.000+01:00
diff --git a/algorithms/src/main/java/com/baeldung/automata/FiniteStateMachine.java b/algorithms/src/main/java/com/baeldung/automata/FiniteStateMachine.java
@@ -0,0 +1,20 @@
+package com.baeldung.automata;
+
+/**
+ * Finite state machine.
+ */
+public interface FiniteStateMachine {
+
+	/**
+	 * Follow a transition, switch the state of the machine.
+	 * @param c Char.
+	 * @return A new finite state machine with the new state.
+	 */
+	FiniteStateMachine switchState(final CharSequence c);
+
+    /**
+     * Is the current state a final one?
+     * @return true or false.
+     */
+    boolean canStop();
+}
diff --git a/algorithms/src/main/java/com/baeldung/automata/RtFiniteStateMachine.java b/algorithms/src/main/java/com/baeldung/automata/RtFiniteStateMachine.java
@@ -0,0 +1,30 @@
+package com.baeldung.automata;
+
+/**
+ * Default implementation of a finite state machine.
+ * This class is immutable and thread-safe.
+ */
+public final class RtFiniteStateMachine implements FiniteStateMachine {
+
+	/**
+	 * Current state.
+	 */
+	private State current;
+
+	/**
+	 * Ctor.
+	 * @param initial Initial state of this machine.
+	 */
+	public RtFiniteStateMachine(final State initial) {
+		this.current = initial;
+	}
+
+	public FiniteStateMachine switchState(final CharSequence c) {
+		return new RtFiniteStateMachine(this.current.transit(c));
+	}
+
+	public boolean canStop() {
+		return this.current.isFinal();
+	}
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/automata/RtState.java b/algorithms/src/main/java/com/baeldung/automata/RtState.java
@@ -0,0 +1,42 @@
+package com.baeldung.automata;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * State in a finite state machine.
+ */
+public final class RtState implements State {
+
+    private List<Transition> transitions;
+    private boolean isFinal;
+
+    public RtState() {
+        this(false);
+    }
+    
+    public RtState(final boolean isFinal) {
+        this.transitions = new ArrayList<>();
+        this.isFinal = isFinal;
+    }
+
+    public State transit(final CharSequence c) {
+        for(final Transition t : this.transitions) {
+            if(t.isPossible(c)) {
+                return t.state();
+            }
+        }
+        throw new IllegalArgumentException("Input not accepted: " + c);
+    }
+
+    public boolean isFinal() {
+        return this.isFinal;
+    }
+
+	@Override
+	public State with(Transition tr) {
+		this.transitions.add(tr);
+		return this;
+	}
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/automata/RtTransition.java b/algorithms/src/main/java/com/baeldung/automata/RtTransition.java
@@ -0,0 +1,31 @@
+package com.baeldung.automata;
+
+
+/**
+ * Transition in finite state machine.
+ */
+public final class RtTransition implements Transition {
+
+	private String rule;
+	private State next;
+	
+	/**
+	 * Ctor.
+	 * @param rule Rule that a character has to meet 
+	 *  in order to get to the next state.  
+	 * @param next Next state.
+	 */
+	public RtTransition (String rule, State next) {
+		this.rule = rule;
+		this.next = next;
+	}
+	
+	public State state() {
+		return this.next;
+	}
+
+	public boolean isPossible(CharSequence c) {
+		return this.rule.equalsIgnoreCase(String.valueOf(c));
+	}
+
+}
diff --git a/algorithms/src/main/java/com/baeldung/automata/State.java b/algorithms/src/main/java/com/baeldung/automata/State.java
@@ -0,0 +1,29 @@
+package com.baeldung.automata;
+
+/**
+ * State. Part of a finite state machine.
+ */
+public interface State {
+
+	/**
+	 * Add a Transition to this state.
+	 * @param tr Given transition.
+	 * @return Modified State.
+	 */
+	State with(final Transition tr);
+
+    /**
+     * Follow one of the transitions, to get 
+     * to the next state.
+     * @param c Character.
+     * @return State.
+     * @throws IllegalStateException if the char is not accepted.
+     */
+    State transit(final CharSequence c);
+    
+    /**
+     * Can the automaton stop on this state?
+     * @return true or false
+     */
+    boolean isFinal();
+}
diff --git a/algorithms/src/main/java/com/baeldung/automata/Transition.java b/algorithms/src/main/java/com/baeldung/automata/Transition.java
@@ -0,0 +1,20 @@
+package com.baeldung.automata;
+
+/**
+ * Transition in a finite State machine.
+ */
+public interface Transition {
+
+	/**
+	 * Is the transition possible with the given character?
+	 * @param c char.
+	 * @return true or false.
+	 */
+	boolean isPossible(final CharSequence c);
+
+	/**
+	 * The state to which this transition leads.
+	 * @return State.
+	 */
+    State state();
+}
diff --git a/algorithms/src/test/java/algorithms/RtFiniteStateMachineTest.java b/algorithms/src/test/java/algorithms/RtFiniteStateMachineTest.java
@@ -0,0 +1,82 @@
+package algorithms;
+
+import static org.junit.Assert.*;
+import org.junit.Test;
+import com.baeldung.automata.*;
+
+/**
+ * Tests for {@link RtFiniteStateMachine}
+ */
+public final class RtFiniteStateMachineTest {
+
+	@Test
+    public void acceptsSimplePair() {
+    	String json = "{\"key\":\"value\"}";
+    	FiniteStateMachine machine = this.buildJsonStateMachine();
+    	for (int i=0;i<json.length();i++) {
+    	    machine = machine.switchState(String.valueOf(json.charAt(i)));
+    	}
+    	assertTrue(machine.canStop());
+    }
+	@Test
+    public void acceptsMorePairs() {
+    	String json = "{\"key1\":\"value1\",\"key2\":\"value2\"}";
+    	FiniteStateMachine machine = this.buildJsonStateMachine();
+    	for (int i=0;i<json.length();i++) {
+    	    machine = machine.switchState(String.valueOf(json.charAt(i)));
+    	}
+    	assertTrue(machine.canStop());
+    }
+	
+	@Test(expected = IllegalArgumentException.class)
+    public void missingColon() {
+    	String json = "{\"key\"\"value\"}";
+    	FiniteStateMachine machine = this.buildJsonStateMachine();
+    	for (int i=0;i<json.length();i++) {
+    	    machine = machine.switchState(String.valueOf(json.charAt(i)));
+    	}
+    }
+
+	/**
+	 * Builds a finite state machine to validate a simple
+	 * Json object.
+	 * @return
+	 */
+	private FiniteStateMachine buildJsonStateMachine() {
+		State first = new RtState();
+    	State second = new RtState();
+    	State third = new RtState();
+    	State fourth = new RtState();
+    	State fifth = new RtState();
+    	State sixth = new RtState();
+    	State seventh = new RtState();
+    	State eighth = new RtState(true);
+
+    	first.with(new RtTransition("{", second));
+    	second.with(new RtTransition("\"", third));
+    	//Add transitions with chars 0-9 and a-z
+    	for (int i = 0; i < 26; i++) {
+    		if(i<10) {
+        	    third = third.with(
+            	    new RtTransition(String.valueOf(i), third)
+            	);
+        	    sixth = sixth.with(
+                	new RtTransition(String.valueOf(i), sixth)
+                );
+    		}
+    	    third = third.with(
+    	        new RtTransition(String.valueOf((char) ('a' + i)), third)
+    	    );
+    	    sixth = sixth.with(
+        	    new RtTransition(String.valueOf((char) ('a' + i)), sixth)
+        	);
+    	}
+    	third.with(new RtTransition("\"", fourth));
+    	fourth.with(new RtTransition(":", fifth));
+    	fifth.with(new RtTransition("\"", sixth));
+    	sixth.with(new RtTransition("\"", seventh));
+    	seventh.with(new RtTransition(",", second));
+    	seventh.with(new RtTransition("}", eighth));
+    	return new RtFiniteStateMachine(first);
+	}
+}
