| Course ID: | CSCI 2670E. 4 hours. |
| Course Title: | Introduction to Theory of Computing |
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 complexity, and NP-completeness and tractability. |
| Oasis Title: | Intro to Theory of Computing |
| Duplicate Credit: | Not open to students with credit in CSCI 2670 |
| Nontraditional Format: | This course will be taught 95% or more online. Lectures will be recorded and posted on eLC. Daily exercises will support the content covered in the videos. Students will access all content on eLC. Regular office hours going over the exercises will be provided online. Exams will be offered online through eLC. |
| Prerequisite: | CSCI 2610 or CSCI 2611 |
| 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: | 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. |