Log in with WebAuth to see who is in the course and view and write course reviews.
CS154 - Introduction to Automata and Complexity Theory
Regular sets: finite automata, regular expressions, equivalences among notations, methods of proving a language not to be regular. Context-free languages: grammars, pushdown automata, normal forms for grammars, proving languages non-context-free. Turing machines: equivalent forms, undecidability. Nondeterministic Turing machines: properties, the class NP, complete problems for NP, Cook's theorem, reducibilities among problems. Prerequisites: 103 or 103B. May be taken for 3 units by graduate students.
GERs: DB-EngrAppSci
Details
Course Website
Sell Your CS154 Book
CourseRank Details
Offerings
2008-2009 Autumn
| Sec | Type | Instructor | Room | Units | Days | Times | ||
|---|---|---|---|---|---|---|---|---|
| 01 | Lecture | David Dill | Herrin T175 | 3-4 | Tue Thu | 3:15-4:30pm |
 Shop
|
2008-2009 Spring
| Sec | Type | Instructor | Room | Units | Days | Times | ||
|---|---|---|---|---|---|---|---|---|
| 01 | Lecture | Rajeev Motwani | TBA | 3-4 | Tue Thu | 3:15-4:30pm |
Shop
|
2008-2009 Summer
| Sec | Type | Instructor | Room | Units | Days | Times | ||
|---|---|---|---|---|---|---|---|---|
| 01 | Lecture | Staff | TBA | 3-4 | Mon Wed | 4:15-6:05pm |
Shop
|
Readings
2007-2008 Autumn
| Sec | Kind | Books | ||
|---|---|---|---|---|
| 01 | Required Material(s) | Hopcroft: | Intro to Automata Theory, Languages & Computation (3rd ed) | $122.00 |
| 01 | Recommended Material(s) | Sipser: | Intro to Theory of Computation (2nd ed) | |
2007-2008 Spring
| Sec | Kind | Books | ||
|---|---|---|---|---|
| 01 | Required Material(s) | Hopcroft: | Intro to Automata Theory, Languages & Computation (3rd ed) | $122.00 |
Wiki
Log in with WebAuth to view the Wiki.