Notes / Section 6
Theory of Computation
Regular expressions and finite automata
Regular expressions and finite automata. Regular languages.
Context-free grammars and PDAs
Context-free grammars and push-down automata. Context-free languages.
Pumping lemma and closure properties
Pumping lemma.
Turing machines and undecidability
Turing machines and undecidability.