Dr. Nagiza Samatova
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.
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.
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.
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.
Grades will be based on:
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.