DFA.java

/**
 * Deterministic finite automata for recognising language of strings with
 * following conditions:
 *
 * 1. It must contain only :, ), (, and _ characters.
 * 2. :has to be followed by ) or (.
 * 3. Has to have at least one smiley :) or sad :( face.
 * 4. If string has more than one face, then all of them have to be separated by at least one _ character.
 * 5. Each string can start and end with zero or more _ characters.
 *
 * @see http://www.dennis-grinch.co.uk/tutorial/dfa-in-java
 * @author Dennis Grinch
 */
public class DFA {

    /**
     * Enum representing set of states Q. Each state has boolean
     * variable "accept" which indicates if it is an accept
     * state or not. All states with "true" accept value
     * represents subset of accept states F.
     * <p>
     * Every state has an instance variable corresponding to the
     * symbol in the subset of alphabet Σ. Thus "eyes" stands for :,
     * smile - for ), sad - for (, and space for _.
     *
     */
    private enum States {

        Q0(false), Q1(false), Q2(true), Q3(true), Q4(false);

        // transition table
        static {
            Q0.eyes = Q1;  Q0.space = Q0;
            Q1.smile = Q2; Q1.sad = Q2;
            Q2.space = Q3;
            Q3.eyes = Q1; Q3.space = Q3;
        }

        States eyes;
        States smile;
        States sad;
        States space;

        final boolean accept;

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

        /**
         * Represents transition function δ : Q × Σ → Q.
         *
         * @param ch is a symbol from alphabet Σ (Unicode)
         * @return state from codomain Q
         *
         */
        States transition(char ch) {
            switch (ch) {
                case ':':
                    return this.eyes == null? Q4 : this.eyes;
                case ')':
                    return this.smile == null? Q4: this.smile;
                case '(':
                    return this.sad == null? Q4: this.sad;
                case '_':
                    return this.space == null? Q4: this.space;
                default:
                    return Q4;
            }
        }

    }

    /**
     * Checks if DFA accepts supplied string.
     *
     * @param string to check
     * @return true if it does accept, false otherwise
     */
    public boolean accept(String string) {
        States state = States.Q0;
        for (int i = 0; i < string.length(); i++) {
            state = state.transition(string.charAt(i));
        }
        return state.accept;
    }
}