The School of Electrical Engineering and Computer Science

Home » Undergraduate Study » Computer Science » Courses

CptS 317: Automata and Formal Languages

Catalog Information
Course Number: 
317
Credits: 
3
Pre-Requisites
CptS 122: Data Structures


Elementary set theory, discrete mathematics.

Dependent Courses: 
Class Information
Objectives: 

Understand fundamental classes of formal languages and computational models and the relationship between them, reason about and prove properties of different language classes, understand limitation of computational process, prepare students for subsequent courses in algorithms, complexity theory, programming languages, and compilers.

Topics: 
  1. Mathematical preliminaries: sets, strings, languages, & induction
  2. Finite automata: deterministic & nondeterministic, their equivalence, & minimization
  3. Regular expressions and languages; closure properties & pumping lemma.
  4. Context-free grammars: sentential forms, derivations, parse trees & ambiguity
  5. Normal forms: Simplification & Chomsky Normal Form
  6. Pushdown automata: deterministic & nondeterministic, translation between CFG & PDA
  7. Context-free languages: properties & pumping lemma
  8. Turing machines: recursive & R.E. languages, Church-Turing thesis
  9. Halting problem
Requirements
Textbooks/References: 

Introduction to Automata Theory, Languages and Computation 2nd Edition (2001). Publisher: Addison-Wesley. Authors: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.

Professor/Coordinator: 
Muralidhar Medidi
Contact us: webmaster@eecs.wsu.edu | Telephone: 509 335 6602 Fax: 509 335 3818 | Accessibility | Copyright | Policies
School of Electrical Engineering and Computer Science, PO BOX 642752, Washington State University, Pullman, WA, 99164-2752 USA