CSC 333 - Automata, Grammars, and ComputabilityCatalog 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.
- Lecture: 3 hours
Coordinator: Dr. Donald Sheehy
Textbook: Introduction to the Theory of Computatio
- 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.
- 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
- 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