Project for CSE 30151 Spring 2009

Projects for CSE 30151 Spring 2009

Project 1: Nondeterministic Finite Automata

General information

Project description - Due on Thursday, February 12, 2009 at 11:59pm

Test files

Project 2: Deterministic Pushdown Automata

General information

Project description - Due on Thursday, March 26, 2009 at 11:59pm

Test files

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

Project 3: (Deterministic) Turing Machines

General information

Project description - Due on Monday, April 20, 2009 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 tm-input1.txt tm-output1.txt
TM that accepts all strings x#x, where x is composed of a's and b's: tm2.txt tm-input2.txt tm-output2.txt
Extra input for tm2.txt that allows to test non-deciders: tm-input3.txt (i.e., processing this string requires more than 1000 steps)