🌁 Nondeterministic Finite State Automata for Java (in plain English: flowcharts with multiple possible outcomes)
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src Add parking meter example Jun 18, 2016
.gitignore Add pom,update readme Oct 30, 2016
.travis.yml
LICENSE.txt First commit Jun 17, 2016
README.md Update README.md Jan 12, 2017
pom.xml Add pom,update readme Oct 30, 2016

README.md

Nondeterministic finite state automata

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.

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:

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:

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.¢ = ¢;
        }
    }
}