 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
Finite State Machines
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
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
|