Course Description
The theory of computing, including finite automata, regular expressions and languages, context-free grammars and languages, push-down automata, pumping lemmas, the Chomsky hierarchy of language classes, Turing machines and computability, undecidability of the halting problem, reducibilities among decision problems and languages, time and space complexity, and NP-completeness and tractability.
Athena Title
Intro to Theory of Computing
Equivalent Courses
Not open to students with credit in CSCI 2670E
Prerequisite
CSCI 2610 or CSCI 2611
Semester Course Offered
Offered fall and spring
Grading System
A - F (Traditional)
Course Objectives
1. Define regular languages using various methods and be able to prove if a language is or is not regular. 2. Define context-free languages using various methods and be able to prove if a language is or is not context-free. 3. Define Turing recognizable languages using various types of Turing machines and be able to prove the different types of machines are equivalent with regard to the languages they accept. 4. Define decidability and be able to prove if a language is decidable or not. 5. Distinguish between P and NP and prove a language is in P or in NP.
Topical Outline
Major Topics Covered 1. Regular Languages a. Given an NFA M, create a DFA or regular expression that accepts L(M). b. Given a regular language L, create an NFA that accepts L. c. Use the pumping lemma for regular languages to prove a language is not regular. 2. Context-free Languages a. Given a description of a context free language L, develop a context free grammar G such that L(G) = L. b. Convert a context free grammar to an equivalent push-down automata and vice-versa. c. Convert a CFG into Chomsky normal form (CNF). d. Given a context-free grammar G in CNF and a string w, use the CYK algorithm to determine if G generates w. e. Use the pumping lemma for context-free languages to prove a language is not context-free. f. Identify if a given language is regular, context-free, or neither. 3. Turing-recognizable Languages a. Given a language L, create a Turing machine that accepts L. b. Convert between the different variations of Turing machines (e.g., multi-tape to single-tape). c. Create a Turing machine that computes a function. 4. Decidability a. Define decidability and determine if a language is decidable. b. Prove that the Halting problem is undecidable. c. Reduce one problem to another. d. Use reductions to prove a problem is undecidable. 5. Computational Complexity a. Define P, NP, and NP-complete b. Show a problem is in P. c. Write pseudo-code describing a non-deterministic Turing machine’s steps to solve a problem. d. Describe the Cook-Levin theorem. e. Describe a verifier for an NP-complete language.
Syllabus