##
CSCE 433 Formal Languages and Automata

Fall 09

**Instructor**: Sing-Hoi Sze

**Email**: shsze@cse.tamu.edu

**Meeting**: MWF 1:50-2:40 HRBB 104

**Office Hours**: MWF 12:50-1:50 HRBB 328B or by appointment

### Textbook

Hopcroft J.E., Motwani R. and Ullman J.D. *Introduction to
Automata Theory, Languages and Computation*. Addison-Wesley.

### Goal

This is an undergraduate level course which 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.

### Topics

- 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,
pumping lemma.
- Turing machines: Turing machines, variants, nondeterministic Turing
machines, decidability and undecidability,
*NP*-completeness.

### Grading

- Homework assignments (30%): short written assignments handed
out every one or two weeks.
- Two midterms (20% each).
- One final exam (30%).