Formal languages and grammars, finite state machines, automata, Turing machines, application to compilers.
Sections 13.1-13.5: Languages and grammars, finite-state machines, language recognition, Turing machines
Textbook 50 pages
Introduction to theory of computation, formal language theory, strings, languages, grammars, automata.
Lecture notes
Deterministic finite automata, state transition diagrams, Moore and Mealy machines, nondeterministic finite automata, regular sets.
Regular sets revisited, regular expressions.
Turing machines, restricted types of automata.
Chomsky hierarchy, models of computation, computational complexity theory.
Phrase-structure grammars, derivation trees, production rules (Rosen Section 13.1)
Problems
Solutions
State diagrams, state tables, state machine design (Rosen Section 13.2)
Deterministic finite-state automatons, language recognition (Rosen Section 13.3)
Regular expressions, regular grammars, (Rosen Section 13.4)
Turing machine execution, construction (Rosen Section 13.5)