In addition to homework assignments, you'll work on projects that let you integrate what you've learned in this course with something (else) that you're interested in.


The project report should have three parts:


Most projects will be papers or programs, or a combination. But if you want to do something else like build hardware or make a video, that's fine too!


Natural Language Processing (CP1 or CP2). Survey applications of finite-state methods,* context-free grammars, or other formalisms to natural language processing.

Mathematical Linguistics (CP2). What class of languages do human languages belong to (finite, regular, context-free, or something else)? Survey the history of this debate. Take a position and argue for it.

  • A similar study could be done of animal communication systems.

Computational Biology (CP1 or CP2). Survey applications of finite-state methods,* context-free grammars, or other formalisms to the analysis of biological sequences (DNA, RNA, or proteins).

Computer Music (CP1 or CP2). Survey applications of finite-state methods* or context-free grammars to analysis or generation of music.

Computer Graphics (CP2 or CP3). Survey formalisms related to those learned in class that have been used for generating computer graphics, like L-systems or Wang tiles.

Programming Languages (CP2 or CP3). Survey uses of finite automata and context-free grammars in programming language compilation, or Turing-equivalent formalisms like the lambda calculus in programming language design, or decidable and undecidable problems in program analysis and verification.

The First Computer (CP3). What was the first computer? Choose an early computer and argue that it was the first true computer and the ones before it were not. Use Turing-equivalence as the definition of a computer – but even under this definition, there's more than one defensible answer to the question.

Super-Turing Computation (CP3). Choose one of the following things that have been claimed to be more powerful than Turing machines.

  • Human intelligence
  • Quantum computation
  • Analog (real) computation
Survey the positions that have been taken for or against it being beyond Turing-equivalent. Take a position and argue for it.

Advanced Topics There are many topics covered in the book or its exercises that we didn't have time for in class. Write a "for dummies" tutorial on one of these.

  • DFA minimization and the Myhill-Nerode Theorem (CP1).
  • Finite transducers (CP1) or synchronous context-free grammars (CP2).
  • Monadic second-order logic over strings and B├╝chi's Theorem (CP1).
  • Deterministic context-free languages (CP2, section 2.4). Note that some of Sipser's terminology differs from the more standard terminology of Knuth.
  • Context-sensitive grammars and linear bounded automata (CP2/3, section 5.1).
  • Lambda calculus (CP3).
  • Cellular automata (CP3).
  • Recursion theorem (CP3, section 6.1).
  • Decidability of logical theories (CP3, section 6.2).
  • Kolmogorov complexity (CP3, section 6.4).

*Finite-state methods go by many different names, including finite-state transducers, hidden Markov models, and conditional random fields.


Applications and Advanced Topics. Many of the topics listed above under "Papers" would also make interesting programming projects; just be sure to choose something manageable. For example:

  • Randomly generate English sentences.
  • Randomly generate music.
  • Generate computer graphics.
  • A lexer/parser for a simple programming language (like Scheme).
  • DFA minimization.
  • Cellular automata.

Tock Extensions. Implement something we learned in class that is not already in Tock. For example:

  • A universal Turing machine (CP3).
  • The constructive proof of the Cook-Levin Theorem, which converts a Turing machine to a sentence of propositional logic.
  • Currently Tock lets you visualize a nondeterministic run as a graph, but maybe an animated and/or interactive visualization would work better.
  • A simple and clean graph editor for state transition diagrams that can be used to create finite automata, pushdown automata, and Turing machines.

Puzzles. In the first lecture, we played with three puzzles that were equivalent to recognition of a regular language, an NP-complete problem, and an undecidable problem. Write an interactive implementation of one of these puzzles, or design a new puzzle.

  • CP2: Design and implement a new puzzle that is equivalent to recognition of a CFL. Probably the best way to do this would be inspired by RNA secondary structure.
  • Optional: Implement an automatic solver.

Example Projects

Here are some web-based projects that students have done in the past. (There have been lots of other great projects, but the web-based ones are easiest to include here.)