Instructor

Dr. Nagiza Samatova

Dr. Nagiza Samatova

Computer Science

Phone: 919-513-7575
Fax: 919-515-7896
Email: samatova@csc.ncsu.edu
Instructor Website

CSC 333 Automata, Grammars, and Computability

3 Credit Hours

Study of three classical formal models of computation--finite state machines, context-free grammars, and Turing machines--and the corresponding families of formal languages. Power and limitations of each model. Parsing. Non-determinism. The Halting Problem and undecidability. The classes P and NP, and NP-completeness.

Prerequisite

Applied Discrete Mathematics (NC State CSC 226) or an equivalent discrete mathematics course (a grade of B or better is strongly recommended). This material is reviewed briefly in the introduction to the text.

Must be comfortable with any programming language, such as Java, Python, C/C++, as there are numerous programming assignments.

Course Objectives

Upon successful completion of this course, a student will be able to:

  • To explain basic models of computation.
  • To reason about strengths and limitations of variable models of computation.
  • To apply these models to provide computational solutions to problems from various fields.

Learning Outcomes:

Part I: Automata Theory:

  • Define formal languages and explain how they can be generated by different automata
  • Synthesize finite and pushdown automata with specific properties
  • Convert among multiple representations of finite and pushdown automata
  • Prove particular problems cannot be solved by finite or pushdown automata using the Pumping Lemma or the closure properties of regular and/or context-free languages

Part II: Computational Theory:

  • Define, and explain the significance of the “P = NP?” question and NP-completeness.
  • Prove lower bounds on time and space complexity using diagonalization and polynomial time reducibility methods.
  • Define deterministic and nondeterministic computation time and space, and explain the relationships among them.
  • Describe concrete examples of NP-complete problems from different fields.
  • Describe concrete examples of decidable problems that are known to be unsolvable in polynomial time.

Part III: Computability Theory:

  • Define computable problems in terms of Turing machines.
  • Describe concrete examples of undecidable problems from different fields.
  • Use the relationship between recognizability and decidability to determine decidability properties of problems.
  • Prove undecidability using diagonalization and reducibility methods.

Course Requirements

Grades will be based on:

Homework 25%
Projects 40%
First Exam 15%
Second Exam 15%
Participation 5%

Textbook

No textbooks are required. The instructor will provide all the relevant materials for the course.

Computer and Software Requirements

Please review minimum computer specifications recommended by NC State University and Engineering Online.

Updated 10/07/2020