CSCE 433/627 Formal Languages and Automata / Theory of Computability
Instructor: Sing-Hoi Sze
Meeting: TR 8-9:15 HRBB 113
Office Hours: TR 9:15-10:15 HRBB 328B or by appointment
Hopcroft J.E., Motwani R. and Ullman J.D. Introduction to
Automata Theory, Languages and Computation. Addison-Wesley.
This course studies formal models of computation and the relationships
between them. The course will focus on the question "what is computable"
versus "what is not computable" in each model.
- Finite automata and regular expressions: deterministic finite automata,
nondeterministic finite automata, regular expressions, equivalence, closure
properties, pumping lemma.
- Context-free grammar and pushdown automata: context-free grammar,
pushdown automata, equivalence, closure properties, Chomsky normal form,
- Turing machines: Turing machines, variants, nondeterministic Turing
machines, decidability and undecidability, NP-completeness.
- Homework assignments (433: 30%; 627: 25%): written assignments handed out
every one or two weeks.
- Two midterms (433: 20% each; 627: 15% each).
- One final exam (433: 30%; 627: 25%).
- Presentation (627: 20%): towards the end of the semester, each 627 student
will give a presentation on a topic of interest.
- 433: junior or senior classification or approval of instructor.
- 627: graduate standing or approval of instructor.