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.