CSCI 672 - Theory of Computation

3 Credits
This course covers the theory of computer science emphasizing automata, grammars computation and their applications in the specification of languages and computer systems, models of computation and complexity. Finite-state machines, pushdown automata, Turing machines, regular expressions, decidability, computational complexity, including classes P, NP, NP-complete, NP-hard, and PSPACE will be explored.

Course Learning Outcomes:
1. Design a finite automaton to recognize a given regular language and a context-free grammar for pushdown automata.
2. Construct pushdown automata and the equivalent context free grammars.
3. Construct finite state machines and the equivalent regular expressions.
4. Evaluate the concepts of computability and the equivalence of languages described by finite state machines and regular expressions.