CS/MATH 300 Home Homework Class Notes Syllabus Bibliography

This document was last modified on March 30, 2009. Jump directly to Models of Computation | Finite State Machines | Context-Free Grammars | Turing Machines | Computability | Complexity Models of Computation Yuri Gurevich at the University of Michigan has proposed abstract state machines as a high-level alternative to Turing machines for a universal model of computation. This web site also provides information on a long list of applications ranging from hardware verification and compiler correctness to object-oriented data models and natural language understanding. Finite State Machines Machines that Eat Your Words - fun with finite state machines! Since the infamous Pentium floating point bug, circuit verification has become one of the hot applications of finite state machines. Finite state machines are also used as a tool to understand object-oriented software and to specify and verify communication protocols. C++ template classes for finite automata have been created to support easy and efficient pattern matching and searching. Context-Free Grammars The Berkeley Restaurant Project (BeRP) is a speech recognition system which includes a context-free grammar as one component. Compiler generation tools (such as Lex, Yacc) use context-free grammars to automatically generate parts of compilers (lexical analyzers, parsers, etc.). Extensions of context-free grammars are used to analyze RNA sequences. One course at the University of Helsinki has students use context-free grammars to analyze and automatically generate music. Turing Machines Andrew Hodges, author of Alan Turing: the Enigma, maintains an extensive web site devoted to the life of Alan Turing. The site also contains a Turing machine applet. Here's another Turing machine applet. Are there really steam-powered Turing machines at the University of Washington? Computability Want to find out about the latest research related to computability? The Computability Theory web page includes links to a bibliographic database, home pages of people working in the area, related conferences, and a paper describing open questions. Some information on NP-completeness from previous years classes. Computational Complexity Many of the games and puzzles people play are interesting because of their computational complexity. Even shoelaces can be the source of computational complexity! To find out about research related to computational complexity, check out the electronic colloquium on the topic (with links to books, conferences, researchers' web pages, bibliographies, etc.) and the column on this topic in the EATCS Bulletin