- Notifications
You must be signed in to change notification settings - Fork3
🌁 Nondeterministic Finite State Automata for Java (in plain English: flowcharts with multiple possible outcomes)
License
digitalheir/java-nfa
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
This is a library that provides an implemention ofnondeterminstic 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.
Downloadthe 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 aforward-backward-like algorithm, we can compute all paths through automatonA originating from stateS, given inputI 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:
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.¢ = ¢; } }}
About
🌁 Nondeterministic Finite State Automata for Java (in plain English: flowcharts with multiple possible outcomes)