Credits: 1 unit (4 credit hours)
Contact Hours: 3 lecture
Instructor: Professor Ge Xia
Last Taught: Spring 2013
Text Book: Introduction to Automata Theory, Languages and Computation, 3rd ed.
By Hopcroft, Motwani, and Ullman. (Addison-Wesley, 2006.)
Description: An introduction to the theoretical foundations of computer science and formal models of computation. Topics include formal languages, finite automata, computability, and undecidability.
Prerequisites: CS202 (Analysis of Algorithms)

Specific Course Goals:

After successfully completing this course, the student will be able to:

  • Understand the basic abstract machine types and the basic types of formal languages; understand the correspondence between the machine types and the languages.
  • Understand the difference between computable and incomputable problems and tractable and intractable problems.

Student Outcomes:

ABET/CAC Outcome 1 Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions.

Topics covered:

  • Finite Automata
    • Deterministic Finite Automata
    • Nondeterministic Finite Automata
    • Finite Automata with Epsilon-Transitions
  • Regular Expressions and Languages
  • Regular Expressions and Their Relationship to Regular Languages
  • Properties of Regular Languages
  • Proving Regularity
  • Closure Properties
  • Decision Problems
  • Automata Equivalence and Minimization
  • Context-Free Grammars
  • Parse Trees and Applications
  • Language and Grammar Ambiguity
  • Pushdown Automata
  • PDA Languages
  • PDA and CFG Equivalence
  • Deterministic PDA
  • Context-Free Languages
  • Normal Forms
  • Pumping-Lemma
  • Closure Properties
  • Decision Properties
  • Turing Machines
  • Definition and Preliminaries
  • Machine Extensions
  • The Restricted Machine
  • Undecidability and undecidable problems
  • P and NP Problem Classes
    • NP-Complete Problems