TO DO list 

Check all of the current software systems in the world for formal languages & automata (DONE) 

1. Grail 

2. FLAP 

3. JFLAP 

4. PATE 

1. Context-Free Grammars 

  a. Dependency graph (DONE) 

      Idea:  

        create an NFA with \lambda edges 

       deltaStarNFA(nfa,A,\lambda) will give the set of Bs where A=>*B 

  b. Remove unit production rules (DONE) 

  c. Remove useless production rules (DONE) 

  d. Parse a string (n^3 CYK algorithm) (DONE) 

  e. Graph of derivation trees for a sentence (DONE) 

  f. Chomsky Normal Form (DONE) 

  g. RE2DFA, RE2NFA (Ryan) 

  h. pattern matching (Ryan) 

2. Push Down Automata (DONE) 

  a. Graph 

  b. Animation for the automata 

3. Turing machines (Input: an unlimited tape which is a table)  

  union of two one-tape DTM => one two-tape DTM 

  complement 

  concatenate 

  (DONE) 

  a. Graph 

  b. Animation for TM 

  c. Multi-tape Turing machines 

    c1. One-tape: [table([-infinity=a,+infinity=b])] 

    c2. Two-tape: [table([-infinity=a,+infinity=b]),table([-infinity=aa,+infinity=bb])] 

    c3. Multi-tape: [table([-infinity=a,+infinity=b]),table([-infinity=aa,+infinity=bb]),...,table([-infinity=aaa,+infinity=bbb])] 

  d. Multi-dimensional tape Turing machines 

    d1. Two-dimensional tape Turing machines [table([(-infinity,-infinity)=a,(+infinity,+infinity)=b])] 

                        (0,1) 

                           ^ 

    (-1,0) <- (0,0) -> (1,0) 

                            v 

                          (0,-1) 

    d2. Three-dimensional tape Turing machines [table([(-infinity,-infinity,-infinity)=a,(+infinity,+infinity,+infinity)=b])] 

          (Left, Right, Up, Down, Forward, Backward, Stay) 

    d3. Capability of having >3-dimensional tape - But it is an unrealistic tape. 

4. Complexity: Peter's algorithm for studying complexity.