### Course Outcomes for CSC 333 - Automata, Grammars, and Computability

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

**Automata Theory:**- Develop skill at stating and proving mathematical statements about formal models of computation.
- Define formal languages and explain how they can be generated by different automata.
- Synthesize finite and pushdown automata with specific properties.
- Convert among multiple representations of finite and pushdown automata.
- Prove particular problems cannot be solved by finite or pushdown automata using the Pumping Lemma or the closure properties of regular and/or context-free languages.

**Computability Theory:**- Define Turing machines and their variants as models of computation.
- Define computable problems in terms of Turing machines.
- Use the relationship between recognizability and decidability to determine decidability properties of problems.
- Prove undecidability using diagonalization and reducibility methods.

**Computational Complexity Theory:**- Define, and explain the significance of, the "P = NP?" question and NP-completeness.
- Define deterministic and nondeterministic computation time and space, and explain the relationships among them.
- Describe concrete examples of NP-complete problems from different fields.

See Course Listings