times since June 11, 2003.
Project ideas are below.
Project Requirements
The CE 160 project grade, normalized to 100 points, shall comprise 40% of the basic class standing.
The 100 points of the project grade are distributed as follows:
- 10 pts for having an approved project proposal by a specified deadline
- 10 pts for 5 progress reports (2 pts per progress report)
- 20 pts for an oral presentation of the written proposal and progress made so far
- 60 pts for the final project defense and project documentation
The Project Proposal
As a minimum the project proposal must provide an introduction to the project, a clear precise statement of the goals of the project, and a clear plan for accomplishing the project.
Progress Reports
Progress reports are required at regular intervals between the time the project has been approved and the deadline for completion of the project and all project documentation. Progress reports are one-page summaries of what has been done since the last progress report (or what has been done since the start of the project, for the first progress report).
Presentation of approved project proposal and project progress
Each project group will present before the class details of their approved project proposal. They shall also present whatever progress they have made so far.
Required documentation at the end of the semester: (details to be finalized)
a softbound hard copy of a formal written report on the project
a CD containing the following:
a copy of the approved proposal
copies of the progress reports
copies of presentation materials used in presenting the project, if any
a soft copy of the formal written report
a website for the project
other forms of documentation as may be appropriate for the particular project
Project Ideas
These are project ideas that you might want to consider. You are not required to choose a project from among the ideas here. Original ideas are most welcome.
Projects involving finite automata
Students working on these projects should come up with a common text file format for specifying DFA's, NFA's, and NFA's with epsilon transitions. Some issues that may arise:
how to specify the alphabet involved; what alphabets are allowed
what are valid formats for state names?
how is the transition function specified?
Write a program that reads text files specifying an NFA or an NFA with epsilon transitions, then produces an equivalent DFA. The specifications for the DFA may then be saved as a text file. Refer to secs. 2.3 and 2.5 of the textbook for a description of NFA's and NFA's with epsilon transitions and their conversion to equivalent DFA's. (at most 3 students)
Write a program that reads a text file specifying a DFA. The user is then allowed to test the behavior of the DFA when given different input strings. The user may also load another DFA. (at most 2 students)
Write a program that reads a text file specifying a DFA, then produces an equivalent DFA with a minimum number of states. The specifications for the optimal DFA may then be saved as a text file. Refer to sec. 4.4 of the textbook. (at most 2 students)
Write a program that reads a text file containing regular expressions. For each regular expression, the program produces one text file specifying an equivalent NFA with epsilon transitions. Refer to sec. 3.2 of the textbook. (at most 2 students)
Write a program that allows a user to specify DFA's, NFA's, and NFA's with epsilon transitions graphically. The program then produces a text file specifying the finite automaton. (at most 8 students)
Write a program that reads a text file specifying a DFA and then generates a circuit using D flipflops and gates, implementing the DFA. Specify the circuit using a text-based netlist format of your choice.(at most 8 students)
Write a program that reads a text file specifying a DFA then produces a regular expression equivalent to the DFA. (at most 4 students)
Write a program that simplifies regular expressions. (at most 4 students)
Projects where lex and/or yacc might be useful (or flex and/or bison)
Write a program that reads an internet RFC file and produces an HTML version of the file with chapters separated into different HTML files hyperlinked with each other. The program automatically identifies Titles and section headings and casts them in bold. The program should work correctly with most RFCs. (at most 8 students)
Write a program that reads text files containing boolean equations and for each boolean equation produces a circuit implementing the boolean equation using NAND gates alone. (at most 4 students)
Write a program that reads text files containing boolean equations and for each boolean equation produces a circuit implementing the boolean equation using NOR gates alone. (at most 4 students)
Write a program that reads text files containing boolean equations and for each boolean equation produces a circuit implementing the boolean equation using XOR gates alone. (at most 6 students)
Design and implement an interpreted language for describing systems of equations, and for specifying elementary row operations on the resulting augmented matrices. The language must allow iteration and conditional execution as a minimum. (at most 8 students)
Projects involving CFGs and PDAs
Students working on these projects should come up with common text file formats for specifying CFGs and PDAs.
Write a program that reads a text file specifying a CFG, then produces an equivalent CFG in Chomsky Normal Form and writes it to a text file. (at most 2 students)
Write a program that reads a text file specifying a CFG in Chomsky Normal Form, then produces an equivalent CFG in Greibach Normal Form and writes it to a text file. The program must verify that the input CFG is really in Chomsky Normal Form. (at most 4 students).
Write a program that reads a text file specifying a CFG, then produces a text file specifying an equivalent PDA. (at most 6 students)
Write a program that reads a text file specifying a PDA, then produces a text file specifying an equivalent CFG. (at most 3 students)
Write a program that reads a text file specifying a PDA, then allows the user to test the PDA on any number of input strings of his choice. Determine if the string is in the language of the PDA, and if so produce an execution trace showing that the string is in the language. (at most 3 students)
Implement the CYK algorithm for testing membership of a string in a CFL specified textually by a CFG. See sec 7.4.4 for a description of the CYK algorithm. (at most 6 students)
Projects involving Turing Machines
Write a program that reads a text file specifying a Turing Machine accepting strings by final state, and allowing the user to test input strings on the Turing Machine. The program displays the sequence of instantaneous descriptions as the string is processed. (at most 6 students)
This page has been accessed
times since June 11, 2003.