- 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)
Topics
Resources
License
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Packages0
Uh oh!
There was an error while loading.Please reload this page.