// Auto.java: create NFA WITH eps-moves
public class Auto {
   int states; // # states
   AutoNode[] a; // main FA data struct
   int maxStates;
   SStack sstack; // simple stack for epsClosure
   int start = 0; // num of start state

   public Auto(int st) {
      sstack = new SStack(50);
      // main FA data structure
      states = st;
      maxStates = st;
      a = new AutoNode[states];
      for (int i = 0; i < states; i++)
         a[i] = new AutoNode();
   }
   
   public void setStart(int state) {
      a[state].start = 1;
      start = state;
   }
   
   public void setMaxStates(int m) {
      maxStates = m;
   }

   public void setTerminal(int state) {
      a[state].terminal = 1;
   }

   // insert: make linked lists of transitions
   public void insert(int state1, char symb, int state2){
      if (a[state1].firstAutoListNode == null) {
         AutoListNode tnode = new AutoListNode(symb,
            state2, null);
         a[state1].firstAutoListNode = tnode;
      }
      else {
         AutoListNode tnode = new AutoListNode(symb,
            state2, a[state1].firstAutoListNode);
         a[state1].firstAutoListNode = tnode;
      }
   }

   // print FA
   public void printA(int s) {
      for (int i = 0; i < s; i++) {
         if (a[i].start == 1) System.out.print("s ");
         else if (a[i].terminal == 1)
            System.out.print("t ");
         else System.out.print("  ");
         if (i < 10) System.out.print(" ");
         System.out.print(i + " --> ");
         AutoListNode tnode = a[i].firstAutoListNode;
         if (tnode == null) System.out.print("\n");
         else
         while (tnode != null) {
            System.out.print("[" + tnode.symb + ",");
            if (tnode.stateNum < 10)
               System.out.print(" ");
            System.out.print(tnode.stateNum + "]");
            tnode = tnode.nextAutoListNode;
            if (tnode != null)System.out.print(" --> ");
            else System.out.print("\n");
         }
      }
      System.out.println();
   }

   public int lookupDFA(int state, char ch) {
      AutoListNode tnode = a[state].firstAutoListNode;
      while (tnode != null) {
         if (tnode.symb == ch) return tnode.stateNum;
         tnode = tnode.nextAutoListNode;
      }
      return -1;
   }

   public void execDFA(String execStr) {
      System.out.println("execDFA: execStr: " + execStr +
        ", states: " + states);
      int loc = 0;
      char curr = execStr.charAt(loc);
      int state = 0;
      while (curr != '$') {
         int nextState = lookupDFA(state, curr);
         if (nextState == -1) err(8);
         if (a[state].start == 1) System.out.print("s ");
         else System.out.print("  ");
         System.out.print(state + " --" + curr + "--> " +
             nextState);
         if (a[nextState].terminal == 1)
            System.out.print(" t");
         System.out.println();
         state = nextState;
         loc++;
         curr = execStr.charAt(loc);
      }

   }

   public void execNFA(String execStr) { // NON-deter
      System.out.println("execNFA: execStr: " + execStr +
        ", states: " + states);
      int[] r;
      int[] s = new int[maxStates];
      // make s a start state
      s[start] = 1;
      printHeader();
      printStates(' ', s);
      s = epsClosure(s);
      printStates(' ', s);
      int loc = 0;
      char curr = execStr.charAt(loc);
      while (curr != '$') {
         int[] t = updateStates(s, curr);
         // printStates(curr, t);
         t = epsClosure(t);
         printStates(curr, t);
         copyStates(s, t);
         loc++;
         curr = execStr.charAt(loc);
      }
   }

   private void copyStates(int[] s, int[] t) {
      for (int i = 0; i < maxStates; i++)
         s[i] = t[i];
   }

   private int[] epsClosure(int[] s) {
      // from 0 to maxStates
      int u;
      int[] color = new int[maxStates]; // wh=0, bl=1
      for (int i = 0; i < maxStates; i++) {
         color[i] = s[i];
         if (color[i] == 1) {
            sstack.push(i);
         }
      }
      while (!sstack.empty()) {
         u = sstack.pop();
         AutoListNode tnode = a[u].firstAutoListNode;
         while (tnode != null) {
            if (tnode.symb == '@') {
               if(color[tnode.stateNum] == 0) {
                  color[tnode.stateNum] = 1;
                  sstack.push(tnode.stateNum);
               }
            }
            tnode = tnode.nextAutoListNode;
         }
      }
      return color;
   }

   private void printHeader() {
      System.out.print(" | ");
      for (int i = 0; i < maxStates; i++) {
         if (i/10 == 0) System.out.print("  ");
         else System.out.print((i/10) + " ");
      }
      System.out.println();
      System.out.print(" | ");
      for (int i = 0; i < maxStates; i++) {
         System.out.print((i%10) + " ");
      }
      System.out.println();
      System.out.print(" | ");
      for (int i = 0; i < maxStates; i++) {
         System.out.print("-" + " ");
      }
      System.out.println();
   }

   private void printStates(char ch, int[] s) {
      int startFlag = 0;
      int terminalFlag = 0;
      System.out.print(ch + ": ");
      for (int i = 0; i < maxStates; i++) {
         System.out.print(s[i] + " ");
         if (s[i] == 1 && a[i].start == 1)
            startFlag = 1;
         if (s[i] == 1 && a[i].terminal == 1)
            terminalFlag = 1;
      }
      System.out.print(" ");
      if (startFlag == 1) System.out.print("s");
      if (terminalFlag == 1)  System.out.print("t");
      System.out.println();
   }

   public int[] updateStates(int[] s, char ch) {
      int[] t = new int[maxStates];
      for (int i = 0; i < maxStates; i++) t[i] = 0;
      for (int i = 0; i < maxStates; i++) {
         // check each occur of ch in list for state i
         // but only for those with s[i] == 1
         if (s[i] == 1) {
            AutoListNode tnode = a[i].firstAutoListNode;
            while (tnode != null) {
               if (tnode.symb == ch || tnode.symb == '.' )
                  t[tnode.stateNum] = 1;
               tnode = tnode.nextAutoListNode;
            }
         }
      }
      return t;
   }

   public int getNumStates() {
      return states;
   }

   private void err(int code) {
      System.out.println("Error " + code);
      System.exit(code);
   }
}
// SStack.java: // int stack, for epsClosure
public class SStack {
   private int size;
   private int[] ss; // main data structure
   private int top;

   public SStack(int s) {
      size = s;
      ss = new int[size];
      top = 0;
   }

   public void push(int i) { ss[top++] = i; }

   public int pop() {
      if (top == 0) return 0;
      return ss[--top];
   }

   boolean empty() { return top == 0; }

   public int size() { return top; }
}

// AutoNode.java
public class AutoNode {
   public AutoListNode firstAutoListNode;
   // other vertex info here
   public int start; // 1 for start state
   public int terminal; // 1 for term state

   public AutoNode() {
      firstAutoListNode = null;
      start = 0;
      terminal = 0;
   }
}
// AutoListNode.java:
public class AutoListNode {
   public char symb; // char being processed
   public int stateNum; // St # after trans
   // next node in linked list
   public AutoListNode nextAutoListNode;

   public AutoListNode(char s, int stateN,
         AutoListNode node) {
      symb = s; 
      stateNum = stateN;
      nextAutoListNode = node;
   }
}
// Auto.java: create NFA WITH eps-moves
public class AutoMain {
   private GetChar getChar;
   private int exNum = 0;

   public AutoMain() {
      getChar = new GetChar();
      exNum = getChar.getNextChar() - '0';
      System.out.println("Ex#: " + exNum);
   }

   public void execExample() {
      if (exNum == 0) { // abb DFA
         Auto auto = new Auto(4);
         auto.setStart(0);
         auto.setTerminal(3);
         auto.insert(0, 'a', 1);
         auto.insert(0, 'b', 0);
         auto.insert(1, 'a', 1);
         auto.insert(1, 'b', 2);
         auto.insert(2, 'a', 1);
         auto.insert(2, 'b', 3);
         auto.insert(3, 'a', 1);
         auto.insert(3, 'b', 0);
         System.out.println("DFA:");
         auto.printA(4);
         auto.execDFA("ababbab$");
      }
      else if (exNum == 1) { // abb NFA
         Auto auto = new Auto(4);
         auto.setStart(0);
         auto.setTerminal(3);
         auto.insert(0, 'a', 0);
         auto.insert(0, 'b', 0);
         auto.insert(0, 'a', 1);
         auto.insert(1, 'b', 2);
         auto.insert(2, 'b', 3);
         System.out.println("NFA:");
         auto.printA(4);
         auto.execNFA("ababbab$");
      }
      else if (exNum == 2) {
         // DFA for (a|b)*(aa|bb)(a|b)*
         Auto auto = new Auto(4);
         auto.setStart(0);
         auto.setTerminal(3);
         auto.insert(0, 'a', 1);
         auto.insert(0, 'b', 2);
         auto.insert(1, 'a', 3);
         auto.insert(1, 'b', 2);
         auto.insert(2, 'a', 1);
         auto.insert(2, 'b', 3);
         auto.insert(3, 'a', 3);
         auto.insert(3, 'b', 3);
         System.out.println("DFA:");
         auto.printA(4);
         auto.execDFA("ababbaaba$");
      }
      else if (exNum == 3) {
         // NFA for (a|b)*(aa|bb)(a|b)*
         Auto auto = new Auto(4);
         auto.setStart(0);
         auto.setTerminal(3);
         auto.insert(0, 'a', 0);
         auto.insert(0, 'b', 0);
         auto.insert(0, 'a', 1);
         auto.insert(0, 'b', 2);
         auto.insert(1, 'a', 3);
         auto.insert(2, 'b', 3);
         auto.insert(3, 'a', 3);
         auto.insert(3, 'b', 3);
         System.out.println("NFA:");
         auto.printA(4);
         auto.execNFA("ababbaaba$");
      }
      if (exNum == 4) {
         // abb DFA, treated as NFA
         Auto auto = new Auto(4);
         auto.setStart(0);
         auto.setTerminal(3);
         auto.insert(0, 'a', 1);
         auto.insert(0, 'b', 0);
         auto.insert(1, 'a', 1);
         auto.insert(1, 'b', 2);
         auto.insert(2, 'a', 1);
         auto.insert(2, 'b', 3);
         auto.insert(3, 'a', 1);
         auto.insert(3, 'b', 0);
         System.out.println("DFA:");
         auto.printA(4);
         auto.execNFA("ababbab$");
      }
      if (exNum == 5) {
         // NFA (a|b)*a(a|b)(a|b)
         Auto auto = new Auto(4);
         auto.setStart(0);
         auto.setTerminal(3);
         auto.insert(0, 'a', 0);
         auto.insert(0, 'b', 0);
         auto.insert(0, 'a', 1);
         auto.insert(1, 'a', 2);
         auto.insert(1, 'b', 2);
         auto.insert(2, 'a', 3);
         auto.insert(2, 'b', 3);
         System.out.println("NFA:");
         auto.printA(4);
         auto.execNFA("aaababbb$");
      }
      if (exNum == 6) {
         // NFA (a|b)*a(a|b)(a|b)(a|b)
         Auto auto = new Auto(5);
         auto.setStart(0);
         auto.setTerminal(4);
         auto.insert(0, 'a', 0);
         auto.insert(0, 'b', 0);
         auto.insert(0, 'a', 1);
         auto.insert(1, 'a', 2);
         auto.insert(1, 'b', 2);
         auto.insert(2, 'a', 3);
         auto.insert(2, 'b', 3);
         auto.insert(3, 'a', 4);
         auto.insert(3, 'b', 4);
         System.out.println("NFA:");
         auto.printA(5);
         auto.execNFA("aaaabaabbababbbb$");
      }
      if (exNum == 7) { //  NFA a*b*c*
         Auto auto = new Auto(3);
         auto.setStart(0);
         auto.setTerminal(2);
         auto.insert(0, 'a', 0);
         auto.insert(0, '@', 1);
         auto.insert(1, 'b', 1);
         auto.insert(1, '@', 2);
         auto.insert(2, 'c', 2);
         System.out.println("NFA:");
         auto.printA(3);
         auto.execNFA("aabbbccab$");
      }
      if (exNum == 8) { //  DFA a*b*c*
         Auto auto = new Auto(4);
         auto.setStart(0);
         auto.setTerminal(0);
         auto.setTerminal(1);
         auto.setTerminal(2);
         auto.insert(0, 'a', 0);
         auto.insert(0, 'b', 1);
         auto.insert(0, 'c', 2);
         auto.insert(1, 'a', 3);
         auto.insert(1, 'b', 1);
         auto.insert(1, 'c', 2);
         auto.insert(2, 'a', 3);
         auto.insert(2, 'b', 3);
         auto.insert(2, 'c', 2);
         auto.insert(3, 'a', 3);
         auto.insert(3, 'b', 3);
         auto.insert(3, 'c', 2);
         System.out.println("DFA:");
         auto.printA(4);
         auto.execDFA("aabbbccab$");
      }
      if (exNum == 9) {
         // NFA (a|b|c)*(ab|aac)
         Auto auto = new Auto(4);
         auto.setStart(0);
         auto.setTerminal(3);
         auto.insert(0, 'a', 0);
         auto.insert(0, 'b', 0);
         auto.insert(0, 'c', 0);
         auto.insert(0, 'a', 1);
         auto.insert(1, 'a', 2);
         auto.insert(1, 'b', 3);
         auto.insert(2, 'c', 3);
         System.out.println("NFA:");
         auto.printA(4);
         auto.execNFA("aabbaaccabc$");
      }
   }

   public int getExNum() {
      return exNum;
   }

   public static void main(String[] args) {
      AutoMain autoMain = new AutoMain();
      autoMain.execExample();
   }
}