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:

1. 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).
2. Synthesize finite automata (DFA/NFA), pushdown automata (PDA), and Turing Machines (TM) to recognize specific languages.
3. Convert representations of languages between different automaton and grammar types (between DFA, NFA, and regular expressions, between CFG and normal form CFG).
4. Construct counter-examples that show particular problems cannot be solved by finite or pushdown automata.
5. Explain, exemplify, and demonstrate uncomputability of specific languages by different automation types (DFA, PDA, Turing machines).
6. 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.
7. 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.
8. 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

See Course Coordinators