eNFA.java

import java.util.*;

/**
 * Nondeterministic finite automaton (ε-NFA) for recognising language of (ab ∪ a)*.
 *
 * @see http://www.dennis-grinch.co.uk/tutorial/enfa
 * @author Dennis Grinch
 */
public class eNFA {

    /**
     * Enum representing set of states Q. Each state has boolean instance variable
     * "accept" which indicates if it is an accept state or not. All states with
     * "true" accept value represents subset of accept states F.
     */
    private enum States {

        Q0(true), Q1(false), Q2(false), Q3(false), Q4(false), Q5(true), Q6(false), Q7(true);

        final boolean accept;

        Set<States> a;
        Set<States> b;
        Set<States> epsilon;

        // transition table
        static {
            Q0.a = Collections.EMPTY_SET;
            Q0.b = Collections.EMPTY_SET;
            Q0.epsilon = new HashSet<>(Arrays.asList(Q1));

            Q1.a = Collections.EMPTY_SET;
            Q1.b = Collections.EMPTY_SET;
            Q1.epsilon = new HashSet<>(Arrays.asList(Q2, Q6));

            Q2.a = new HashSet<>(Arrays.asList(Q3));
            Q2.b = Collections.EMPTY_SET;
            Q2.epsilon = Collections.EMPTY_SET;

            Q3.a = Collections.EMPTY_SET;
            Q3.b = Collections.EMPTY_SET;
            Q3.epsilon = new HashSet<>(Arrays.asList(Q4));

            Q4.a = Collections.EMPTY_SET;
            Q4.b = new HashSet<>(Arrays.asList(Q5));
            Q4.epsilon = Collections.EMPTY_SET;

            Q5.a = Collections.EMPTY_SET;
            Q5.b = Collections.EMPTY_SET;
            Q5.epsilon = new HashSet<>(Arrays.asList(Q1));

            Q6.a = new HashSet<>(Arrays.asList(Q7));
            Q6.b = Collections.EMPTY_SET;
            Q6.epsilon = Collections.EMPTY_SET;

            Q7.a = Collections.EMPTY_SET;
            Q7.b = Collections.EMPTY_SET;
            Q7.epsilon = new HashSet<>(Arrays.asList(Q1));
        }

        // Constructor for state. Every state is either accepting or not.
        States(boolean accept) {this.accept = accept;}

        /**
         * Represents transition function δ : Q × Σ ∪ {ε} → P(Q).
         *
         * @param ch symbol from alphabet, Σ = {a, b}
         * @return set of states
         */
        Set<States> transition(char ch) {
            switch (ch) {
                case 'a':
                    return this.a;
                case 'b':
                    return this.b;
                default:
                    return Collections.EMPTY_SET;
            }

        }

        /**
         * Represents ε-closure.
         *
         * @return ε-closure of this state.
         */
        Set<States> eClose() {
            Set<States> states = new HashSet<>();
            states.add(this);

            for(States e: this.epsilon)
                states.addAll(e.eClose());

            return states;
        }

    }

    /**
     * Checks if εNFA accept string or not
     *
     * @param string to check
     * @return true if yes, false otherwise
     */
    public boolean accept(String string) {
        Set<States> currStates = new HashSet<>(States.Q0.eClose());

        for (int i = 0; i < string.length(); i++)
            currStates = union(currStates, string.charAt(i));

        return currStates.stream().anyMatch(s -> s.accept);
    }

    // helper function which returns set of next states
    private Set<States> union(Set<States> currStates, char ch) {
        Set<States> nextStates = new HashSet<>();

        for (States cState : currStates)
            for(States s: cState.transition(ch))
                nextStates.addAll(s.eClose());
        return nextStates;
    }
}