 | Graduate Course Descriptions
CSE206 - Automata, Formal Languages, and Computability
(Deleted Fall 2002)
Units: 4
Course Description:
Finite automata: non-determinism, regular expressions, regular grammars, 2-way FSAs, minimal state FSAs, context-free languages: normal forms, pumping lemmas, recognition algorithms, push-down automata, DCFLs. Turing Machines; variations on TMs, recursive and r.e. sets, universal TMs, Church's thesis, diagonalization, reducibility, Chomsky Hierarchy.
Prerequisites:
CSE 165 or equivalent consent of instructor.
| |
