Lab2 (from last year)

Lab2.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

public class Lab2 {
	public interface Regex {
		<T> T accept (Visitor<T> v);
	}
	public interface Visitor<T> {
		T visit (EmptySet regex);
		T visit (Symbol regex);
		T visit (Alternation regex);
		T visit (Catenation regex);
		T visit (KleeneClosure regex);
	}
	/** Empty set */
	public static class EmptySet implements Regex {
		public <T> T accept (Visitor<T> v) { return v.visit (this); }
	}
	public static Regex emptySet() { return new EmptySet(); }
	
	/** Symbol */
	public static class Symbol implements Regex {
		public Character symbol; // For empty string, symbol = null
		Symbol (Character c) { symbol = c; }
		public <T> T accept (Visitor<T> v) { return v.visit (this); }
	}
	public static Regex symbol (Character c) { return new Symbol (c); }
	
	/** Alternation */
	public static class Alternation implements Regex {
		public LinkedList<Regex> nodes = new LinkedList<Regex> ();
		public Alternation (Regex ... nodes) {
			for (Regex n : nodes) this.nodes.add (n);
		}
		public <T> T accept (Visitor<T> v) { return v.visit (this); }
	}
	public static Regex alternation (Regex ... nodes) { return new Alternation (nodes); } 
	
	/** Catenation */
	public static class Catenation implements Regex {
		public LinkedList<Regex> nodes = new LinkedList<Regex> ();
		public Catenation (Regex ... nodes) {
			for (Regex n : nodes) this.nodes.add (n);
		}
		public <T> T accept (Visitor<T> v) { return v.visit (this); }
	}
	public static Regex catenation (Regex ... nodes) { return new Catenation (nodes); }
	
	/** Kleene closure */
	public static class KleeneClosure implements Regex {
		public Regex node;
		public KleeneClosure (Regex node) { this.node = node; }
		public <T> T accept (Visitor<T> v) { return v.visit (this); }
	}
	public static Regex kleeneClosure (Regex node) { return new KleeneClosure (node); }

	/* TODO: Implement here */
	public static Regex positiveClosure (Regex r) {
		return null;
	}
	public static Regex times (Regex r, int k) {
		return null;
	}
	public static Regex string (String str) {
		return null;
	}
	public static Regex digit () {
		return null;
	}
	public static Regex alpha () {
		return null;
	}
	public static Regex wentworthEmail () {
		return null;
	}
	
	/** Regex to string */
	public static class StringVisitor implements Visitor<String> {
		public String visit (EmptySet regex) { return "{}"; }
		public String visit (Symbol regex) { 
			return (regex.symbol != null) ? "" + regex.symbol : "λ";
		}
		public String visit (Alternation alternation) {
			StringBuilder sb = new StringBuilder ();
			sb.append ("(");
			sb.append (alternation.nodes.get (0).accept (this));
			for (int i = 1; i < alternation.nodes.size (); i++) {
				sb.append ("|");
				sb.append (alternation.nodes.get (i).accept (this));
			}
			sb.append(")");
			return sb.toString();
		}
		public String visit (Catenation catenation) {
			StringBuilder sb = new StringBuilder ();
			for (Regex node : catenation.nodes)
				sb.append (node.accept (this));
			return sb.toString();
		}
		public String visit (KleeneClosure kleeneClosure) {
			StringBuilder sb = new StringBuilder ();
			sb.append ("(");
			sb.append (kleeneClosure.node.accept (this));
			sb.append (")");
			sb.append ("*");
			return sb.toString();
		}
	}
	public static String regexToString (Regex r) { return r.accept(new StringVisitor()); }
	
	/** Finite automata */
	public static class StateCharacter {
		public State s; public Character c;
		public StateCharacter (State s, Character c) { this.s = s; this.c = c; }
	}
	public static class State {}
	public abstract static class FiniteAutomaton<T> {
		public Set<Character> alphabet = new HashSet<Character> ();
		public Set<State> states = new HashSet<State> ();
		public final State startState = new State ();
		public Map<StateCharacter, T> transitions = new HashMap<StateCharacter, T> ();
		public Set<State> acceptStates = new HashSet<State> ();
		public void addTransition (State fromState, Character character, State toState) {
			alphabet.add (character);
			states.add (fromState);
			states.add (toState);
		}
		public void addAcceptingState (State s) { acceptStates.add (s); states.add (s); }
		public void merge (FiniteAutomaton<T> other) {
			alphabet.addAll(other.alphabet);
			states.addAll (other.states);
			transitions.putAll (other.transitions);
		}
	}
	public static class NFA extends FiniteAutomaton<Set<State>> {
		public void addTransition (State fromState, Character character,
				State toState) {
			super.addTransition (fromState, character, toState);
			Set<State> nextStates;
			StateCharacter from = new StateCharacter (fromState, character);
			if (transitions.containsKey (from)) {
				nextStates = transitions.get (from);
				nextStates.add (toState);
			} else {
				nextStates = new HashSet<State> ();
				nextStates.add (toState);
				transitions.put (new StateCharacter (fromState, character), nextStates);
			}
		}
	}
	/* TODO: Implement here (Next step 2) */
	public static boolean recognize (NFA nfa, String str) {
		return false;
	}
	public static class DFA extends FiniteAutomaton<State> {
		public void addTransition (State fromState, Character character,
				State toState) {
			super.addTransition (fromState, character, toState);
			transitions.put (new StateCharacter (fromState, character), toState);
		}
	}
	/* TODO: Implement here (Next step 1) */
	public static DFA makeDeterministic (NFA nfa) {
		return null;
	}
	public static boolean recognize (DFA dfa, String str) {
		return false;
	}
	public static class RegexToNFA implements Visitor<NFA> {
		public NFA visit (EmptySet regex) { return new NFA (); }
		public NFA visit (Symbol regex) {
			NFA result = new NFA ();
			State end = new State ();
			result.addTransition (result.startState, regex.symbol, end);
			result.addAcceptingState (end);
			return result;
		}
		/* TODO: Implement here */
		public NFA visit (Alternation regex) {
			return null;
		}
		public NFA visit (Catenation regex) {
			return null;
		}
		public NFA visit(KleeneClosure regex) {
			return null;
		}
	}
	public static NFA regexToNFA (Regex r) {
		RegexToNFA converter = new RegexToNFA ();
		return r.accept (converter);
	}
	public static String render (NFA fa) {
		StringBuilder sb = new StringBuilder ();
		sb.append ("digraph NFA {\nrankdir=LR;\n");
		sb.append ("node [style=invisible]; ");
		sb.append (" state_");
		sb.append (fa.startState.hashCode ());
		sb.append (";\n");
		sb.append ("node [style=solid,shape=doublecircle,fontsize=2];");
		for (State s : fa.acceptStates) {
			sb.append (" state_");
			sb.append (s.hashCode ());
		}
		sb.append(";\nnode [shape=circle];\n");
		for (StateCharacter sc : fa.transitions.keySet ()) {
			for (State s : fa.transitions.get (sc)) {
				sb.append ("state_");
				sb.append (sc.s.hashCode ());
				sb.append (" -> ");
				sb.append ("state_");
				sb.append (s.hashCode ());
				sb.append (" [ label = \"");
				sb.append ((sc.c != null) ? sc.c : "λ");
				sb.append ("\" ];\n");
			}
		}
		sb.append ("}");
		return sb.toString ();
	}
	public static String render (DFA fa) {
		StringBuilder sb = new StringBuilder ();
		sb.append ("digraph NFA {\nrankdir=LR;\n");
		sb.append ("node [style=invisible]; ");
		sb.append (" state_");
		sb.append (fa.startState.hashCode ());
		sb.append (";\n");
		sb.append("node [style=solid,shape=doublecircle,fontsize=2];");
		for (State s : fa.acceptStates) {
			sb.append (" state_");
			sb.append (s.hashCode ());
		}
		sb.append(";\nnode [shape=circle];\n");
		for (StateCharacter sc : fa.transitions.keySet ()) {
			sb.append ("state_");
			sb.append (sc.s.hashCode ());
			sb.append (" -> ");
			sb.append ("state_");
			sb.append (fa.transitions.get (sc).hashCode ());
			sb.append (" [ label = \"");
			sb.append ((sc.c != null) ? sc.c : "λ");
			sb.append ("\" ];\n");
		}
		sb.append ("}");
		return sb.toString ();		
	}
	public static void main(String[] args) {
		Regex r = kleeneClosure (catenation (symbol ('A'),symbol ('B')));
		System.out.print ("# ");
		System.out.println (regexToString (r));
		NFA nfa = regexToNFA (r);
		System.out.println (render (nfa));
//		System.out.println (recognize (nfa, "ABAB")); // should print true
//		System.out.println (recognize (nfa, "AAA"));  // should print false
	}
}