##
CSCE 433/627 Formal Languages and Automata / Theory of Computability

Spring 14

**Instructor**: Sing-Hoi Sze

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

**Meeting**: TR 8-9:15 HRBB 113

**Office Hours**: TR 9:15-10:15 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 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.

### 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 (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.

### Prerequisites

- 433: junior or senior classification or approval of instructor.
- 627: graduate standing or approval of instructor.