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

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

  1. Automata Theory:
    1. Develop skill at stating and proving mathematical statements about formal models of computation.
    2. Define formal languages and explain how they can be generated by different automata.
    3. Synthesize finite and pushdown automata with specific properties.
    4. Convert among multiple representations of finite and pushdown automata.
    5. 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.
  2. Computability Theory:
    1. Define Turing machines and their variants as models of computation.
    2. Define computable problems in terms of Turing machines.
    3. Use the relationship between recognizability and decidability to determine decidability properties of problems.
    4. Prove undecidability using diagonalization and reducibility methods.
  3. Computational Complexity Theory:
    1. Define, and explain the significance of, the "P = NP?" question and NP-completeness.
    2. Define deterministic and nondeterministic computation time and space, and explain the relationships among them.
    3. Describe concrete examples of NP-complete problems from different fields.

See Course Listings

See Course Coordinators