Project for CSE 30151 Spring 2008

Project for CSE 30151 Spring 2008

Project 1: Deterministic Finite Automata

General information

Project description - Due on February 8, 2008 at 11:59pm

Test files

Project 2: Deterministic Pushdown Automata

General information

Project description - Due on March 28, 2008 at 11:59pm

Test files

A working DPDA: dpda.txt input.txt output.txt
A non-deterministic machine (should trigger an error): pda2.txt
Another non-deterministic machine: pda3.txt
Another working DPDA: dpda4.txt input4.txt output4.txt

Project 3: (Deterministic) Turing Machines

General information

Project description - Due on May 1, 2008 at 11:59pm

Test files

TM from project 3 description (it accepts all strings x#y where x and y are binary strings and y is longer than x) tm1.txt input-tm1.txt output-tm1.txt
TM that accepts all strings x#x, where x is composed of a's and b's: tm2.txt input-tm2.txt output-tm2.txt
Extra input for tm2.txt that allows to test non-deciders: input-tm3.txt (i.e., processing this string requires more than 1000 steps)