### CSC 333 - Automata, Grammars, and Computability

**Catalog Description:**

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.

**Contact Hours:**

- Lecture: 3 hours

**Prerequisites:**Grade of C or better in either MA225 or CSC226

**Co-requisites:**None

**Restrictions:**None

**Coordinator:**Dr. Donald Sheehy

**Textbook:**Introduction to the Theory of Computatio

**Course Outcomes:**

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

- Explain and formally specify basic automaton types (finite state, pushdown, and Turing machines, both deterministic and nondeterministic), basic formal language types (regular, context-free, decidable, recognizable), and basic formal grammar types (regular expressions and context-free grammars).
- Synthesize finite automata (DFA/NFA), pushdown automata (PDA), and Turing Machines (TM) to recognize specific languages.
- Convert representations of languages between different automaton and grammar types (between DFA, NFA, and regular expressions, between CFG and normal form CFG).
- Construct counter-examples that show particular problems cannot be solved by finite or pushdown automata.
- Explain, exemplify, and demonstrate uncomputability of specific languages by different automation types (DFA, PDA, Turing machines).
- Define measures of deterministic and nondeterministic computation time and space, the notions of deterministic (P) and nondeterministic (NP) polynomial running time, and explain the significance of the P=NP? question.
- Define the notion of NP-completeness, explain its significance for the P=NP? question, and demonstrate NP-completeness of specific problems by reduction from problems known to be NP-complete.
- Describe concrete and common examples of real-world NP-complete problems from different fields.

**Topics:**

- Deterministic Finite Automata
- Nondeterministic Finite Automata
- Regular Languages
- Regular Expressions
- Nonregular Languages
- Context-Free Grammars
- Pushdown Automata
- Non-Context-Free Languages
- Turing Machines
- The Church-Turing Thesis
- Turing Machine Variants
- Decidability
- The Halting Problem and Undecidable Languages
- Time Complexity of Algorithms
- The Classes P and NP
- The Theory of NP-Completeness
- NP-Completeness Reductions

See Course Listings