Instructor

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.