Build Status GitHub version License
This is a library that provides an implemention of nondeterminstic finite state automata (NFAs) in Java. You can think of NFAs as flowcharts: you are in a state, take some action, and arrive in a new state. The action can produce a side effect, such as writing a string to a tape.
Download the latest JAR or grab from Maven:
<dependencies> <dependency> <groupId>org.leibnizcenter</groupId> <artifactId>nfa</artifactId> <version>1.0.0</version> </dependency> </dependencies>
or Gradle:
compile 'org.leibnizcenter:nfa:1.0.0'There are already a bunch of libraries out there which work with deterministic finite state automata (DFAs), and there is a well-known result in automata theory which says that for any language recognized by an NFA, we can construct a DFA which recognizes the same language.
So why not just use DFAs? Two reasons:
- Determinizing an NFA has an exponential blowup in the number of states.
- An NFA may have side-effects, which may be problematic with the standard way of determinizing NFAs. Indeed, some non-deterministic finite state transducers have no equivalent deterministic finite state transducer.
On a side note, Allauzen & Mohri have described efficient algorithms for determining when a transducer is in fact determinizable, and this would be a nice feature to implement.
- Arbitrary input tokens, and arbitrary side effect to state transitions. For example we may implement a finite state transducer by taking strings as input tokens and writing some output string to tape as a side effect.
- Compute possible transition paths in polynomial time! Using a forward-backward-like algorithm, we can compute all paths through automaton A originating from state S, given input I all possible paths in O(|S| * |I| * |A|).
- Transition paths can be accessed through a Spliterator: Java 8 streaming APIs can automatically branch transition paths on states where one action may lead to multiple result states.
Here is a simple example of a parking meter that takes money:
public class ParkingMeter { /** * How much money is in the machine */ private int ¢¢¢; public static void main(String[] args) { // Run example new ParkingMeter().run(); } public void run() { // Say we can buy parking for 100 cents // Define some actions CoinDrop drop25cents = new CoinDrop(25); CoinDrop drop50cents = new CoinDrop(50); // Define our NFA NFA<PayState, CoinDrop> nfa = new NFA.Builder<PayState, CoinDrop>() .addTransition(PAYED_0, drop25cents, PAYED_25) .addTransition(PAYED_0, drop50cents, PAYED_50) .addTransition(PAYED_25, drop25cents, PAYED_50) .addTransition(PAYED_25, drop50cents, PAYED_75) .addTransition(PAYED_50, drop25cents, PAYED_75) .addTransition(PAYED_50, drop50cents, PAYED_0) .addTransition(PAYED_75, drop25cents, PAYED_0) .addTransition(PAYED_75, drop50cents, PAYED_0) // Payed too much... no money back! .build(); // Apply action step-by-step Collection<State> endStates1 = nfa.start(PAYED_0) .andThen(drop25cents) .andThen(drop50cents) .andThen(drop50cents) .andThen(drop25cents) .getState().collect(Collectors.toList()); // Or apply actions in bulk (this makes calculations of the possible paths more efficient, but it doesn't matter if we iterate over all transitions anyway) Collection<State> endStates2 = nfa.apply(PAYED_0, new LinkedList<>(Arrays.asList(drop50cents, drop25cents, drop50cents, drop25cents))) .collect(Collectors.toList()); System.out.println("Today earnings: ¢" + ¢¢¢ + "."); } private class CoinDrop implements Event<PayState> { final int ¢; CoinDrop(int value) { this.¢ = value; } @Override public void accept(PayState from, PayState to) { System.out.println("Bleep Bloop. Added ¢" + ¢ + " to ¢" + from.¢ + ". "); if (to.¢ <= 0 || to.¢ >= 100) System.out.println("You may park. Good day."); else System.out.println("You have paid ¢" + to.¢ + " in total. Please add ¢" + (100 - to.¢) + " before you may park."); System.out.println("----------------------------------------------"); ¢¢¢ += this.¢; } @Override public String toString() { return "¢" + ¢; } } enum PayState implements State { PAYED_0(0), PAYED_25(25), PAYED_50(50), PAYED_75(75); public int ¢; PayState(int ¢) { this.¢ = ¢; } } }