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

CSC 226 Applied Discrete Mathematics 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. A student taking CSC 333 must either be a CSC major or have a GPA of at least 2.75.

Must be comfortable with Java. We will have several programming projects including compiler design and implementation.

• 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 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