General Computability Links

• Course lecture notes. Contain a lot of graphics and mostly cover same material as in course. Useful in case you are stuck with a concept, or had to miss a lecture. Remember that what you're responsible for what was covered in class, and to ignore any due dates or other dated references in these notes.

Finite Automata and Regular Expressions

• An open source program for drawing graphs - useful for automata: Graphviz by AT&T. Link submitted by Amittai Aviram.
• You're encouraged to experiment with the ABCEZ automaton applet and even use it to print your answers The ABCEZ applet was created at Columbia by John E. Cao, Jing Fan, Jing Huang, Shen Li, Yiting Shen and Simin Wang --collectively known as "Mindspring". This was part of a course software project in CS 3156 (Software Engineering) in which Zeph Grunschlag was the client.
• If you'd rather run the Finite Automaton module for creating, running and even saving your automata, you can get it from the Lecture 2 link.
• Java Formal Languages and Automata Package (JFLAP) - Useful Java tool that allows you to build automata, test out their functionality, and easily modify them.
• Finite State Automaton Applet - Automatan simulator, similar to JFLAP. Requires Java.
• java.sun.com - If you need to run Java programs (such as JFLAP) and don't have Java installed, it can be obtained here.
• A HUGE list of finite state automata related research and applications. Thanks to Vadim Lyubashevsky for the link.
• Would you like to play around with egrep on your Windows PC? I suggest that you install the free UNIX environment for Windows called Cygwin which includes many UNIX utilities, including egrep. You'll also need to install this program if you want to run emacs on a Windows PC.

Context Free Grammars

• cfgrep - context free variant of egrep written by Zeph Grunschlag
• JavaCFG. This program (written by Zeph Grunschlag and Yoav Hirsch) has two main functionalities:
  1. Allows user to see if a string is accepted in an (almost) arbitrary grammar and view the parse-tree in two ways.
  2. Allows user to convert a grammar into equivalent forms such as epsilon-free and into Chomsky normal form.
  You can use it experimentally for your homework, and also draw any required parse-trees with it.
• PDA Simulator. If you want to download and run locally you have to fix a couple of their source code path errors. Here are the fixing instructions:
  1. Download the zip file
  2. Unzip "automata.zip" creating the directory "automata"
  3. Move into that new directory
  4. Run the following commmands:

     javac -classpath jpt.jar XHashtable.java XVector.java
     jar -xvf jpt.jar
     mv X*.class edu/neu/ccs/.
     rm jpt.jar XHashtable.java XVector.java
     jar -cvf jpt.jar edu
     

  5. Using your favorite text editor, edit the file "PathNode.java"
  6. Go to line 81 and remove the extra semi-colon in "target.getName();;"
  7. Save the file and exit your text editor.
  8. Run the command:

     javac AutomataApplication.java
     

  9. Run the program with the command:

     java AutomataApplication
     

• The specification of Java, using context free grammars.
• The specification of URL's, using context free grammars.

Turing Machines

• JasTeX → Turing Machine → Simulation by B.J. Dweck. You can draw your TM under the "Drawing" tab, then click on the "Turing Machine Applet" tab to run the Skinner-TM on specific inputs. Try out some examples.
• by Suzanne Skinner. This is my favorite applet and is closer to the TM's in Sipser's book (though not as cute as the next applet). To use:
  1. Paste the TM instructions into the "Programming" text area. For example, for a TM which transforms strings of the form a+(b|c)* which moves all the b's to the left of the c's copy in the following instructions:

     1,a,1,>
     1,b,5,>
     1,c,6,>
     2,a,1,>
     2,b,3,<
     2,c,2,<
     3,a,1,>
     3,b,3,<
     3,c,4,b,>
     4,b,2,c,<
     5,b,5,>
     5,c,6,>
     6,b,7,>
     6,c,6,>
     6,_,H,<
     7,b,7,>
     7,c,7,>
     7,_,2,<
         

     Link to explanation of the instructions.
  2. Then put the initial tape contents in the text field labeled "Initial characters on" (e.g. try aaaabcbcbcbc)
  3. Hit the "Install Program" button
  4. Choose the speed you want and hit the "Start" button
  EXAMPLE Skinner TM's:
  • Even length palindromic bitstrings.
  • Input/Output TM example for squaring unary numbers which illustrates how subroutines can be used inside of TM's.
  • Decider for L where

    L = (xy)^*(ε ∪ x) where [ x = 0ⁿ and y = 1ⁿ ] OR [ x = 1ⁿ and y = 0ⁿ ] .

  • Decimal to Binary translator
• More applets:
  • TM applet. Simple to use:
    1. Write rules down in "Rule List" area
    2. Hit "UPDATE" button
    3. Rules have the form: q₁ x q₂ D where:
       • q₁ is the current state (a number)
       • x is the current state (a char)
       • q₂ is the subsequent state (a number)
       • D is a directive which is one of:
         • < for moving left
         • > for moving right
         • y (any char) for replacing x by y without moving the head
    4. Enter input into the tape
    5. Reposition the head to the start position (by clicking on arrows)
    6. Hit "Step" for one step, or "Auto" or "FastAuto" to run automatically.
  • Visual Turing Machines - Have fun manipulating your own visual, colorful Turing machines
  • Alan Turing - A biography on the man who provided us with the Turing machine
  • Turing Machine Simulator - another downloadable Turing machine, for text-based DOS consoles.
  • by David Eck
  • by H. Weber

P vs. NP