CSC 333 Automata, Grammers and Computability

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. 3 credit hours.


• Prerequisite

Grade of C or better in CSC 226 Discrete Mathematics.

• Course Objectives

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

  1. Automata Theory:
    1. Develop skill at stating and proving mathematical statements about formal models of computation.
    2. Define formal languages and explain how they can be generated by different automata.
    3. Synthesize finite and pushdown automata with specific properties.
    4. Convert among multiple representations of finite and pushdown automata.
    5. 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.
  2. Computability Theory:
    1. Define Turing machines and their variants as models of computation.
    2. Define computable problems in terms of Turing machines.
    3. Use the relationship between recognizability and decidability to determine decidability properties of problems.
    4. Prove undecidability using diagonalization and reducibility methods.
  3. Computational Complexity Theory:
    1. Define, and explain the significance of, the "P = NP?" question and NP-completeness.
    2. Define deterministic and nondeterministic computation time and space, and explain the relationships among them.
    3. Describe concrete examples of NP-complete problems from different fields.

• Course Requirements

Grades will be based 50% on the Projects in Java, 15% on the Homework, 5% on the Lecture Assignments,  15% on the mid-term exam, and 15% on the final exam. Exams are non-comprehensive. All exams are home-take exams, with three business days to complete each exam.

• Textbook

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

• Computer and Internet Requirements

NCSU and Engineering Online have recommended minimum specifications for computers. For details, click here.

• Instructor
  Dr. Nagiza Samatova, Professor
Computer Science-Engineering
2272 EBII
NCSU Campus
Raleigh, NC 27695

Phone: 919-513-7575