| |
|
Lecture Slides for CSCI 550 (Theory of Computing) |
| |
| |
|
CONTENT |
SLIDESHOW |
|
NOTES |
|
| |
| |
|
Chapter 1: Automata - The Methods and the Madness
|
|
|
|
|
|
Chapter 2: Finite Automata
|
|
|
|
|
|
Chapter 3: Regular Expressions and Languages
|
|
|
|
|
|
Chapter 4: Properties of Regular Languages
|
|
|
|
|
|
Chapter 5: Context-Free Grammars and Languages
|
|
|
|
|
|
Chapter 6: Pushdown Automata
|
|
|
|
|
|
- Composite symbols in the PDA-to-CFG Algorithm
|
|
|
|
|
|
Chapter 7: Properties of Context-Free Languages
|
|
|
|
|
|
- The CYK (Dynamic Programming) Algorithm
|
|
|
|
|
|
Chapter 8: Introduction to Turing Machines
|
|
|
|
|
|
- A Universal Turing Machine (UTM)
|
|
|
|
|
|
Chapter 9: Undecidability
|
|
|
|
|
|
Chapter 10: Intractable Problems
|
|
|
|
|
|
Chapter 11: Additional Classes of Problems
|
|
|
|
|
| |
| |
|
Supplement: Automaton-based String Matching
|
|
|
|
|
| |
| |