Nondeterministic finite state automata

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.

Usage

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'

Why?

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.

Current features

• 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.

Example

Here is a simple example of a parking meter that takes money:

publicclassParkingMeter {
/** * How much money is in the machine */privateint ¢¢¢;
publicstaticvoidmain(String[] args) {
// Run examplenewParkingMeter().run();
}
publicvoidrun() {
// Say we can buy parking for 100 cents// Define some actionsCoinDropdrop25cents = newCoinDrop(25);
CoinDropdrop50cents = newCoinDrop(50);
// Define our NFANFA<PayState, CoinDrop> nfa = newNFA.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-stepCollection<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, newLinkedList<>(Arrays.asList(drop50cents, drop25cents, drop50cents, drop25cents)))
.collect(Collectors.toList());
System.out.println("Today earnings: ¢" + ¢¢¢ + ".");
}
privateclassCoinDropimplementsEvent<PayState> {
finalint ¢;
CoinDrop(intvalue) {
this.¢ = value;
}
@Overridepublicvoidaccept(PayStatefrom, PayStateto) {
System.out.println("Bleep Bloop. Added ¢" + ¢ + " to ¢" + from.¢ + ". ");
if (to.¢ <= 0 || to.¢ >= 100) System.out.println("You may park. Good day.");
elseSystem.out.println("You have paid ¢" + to.¢ + " in total. Please add ¢" + (100 - to.¢) + " before you may park.");
System.out.println("----------------------------------------------");
¢¢¢ += this.¢;
}
@OverridepublicStringtoString() {
return"¢" + ¢;
}
}
enumPayStateimplementsState {
PAYED_0(0), PAYED_25(25), PAYED_50(50), PAYED_75(75);
publicint ¢;
PayState(int ¢) {
this.¢ = ¢;
}
}
}