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.
     
Prerequistes:   CS202 (Analysis of Algorithms) and
PHIL200 (Logic)

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.
    (ABET/CAC Outcome A)
  • Understand the difference between computable and incomputable problems and tractable and intractable problems.
    (ABET/CAC Outcome A)

Student Outcomes:

  ABET/CAC Outcome A   An ability to apply knowledge of computing and mathematics appropriate to the program’s student outcomes and to the discipline.

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