Automata Theory and Formal Languages
Description: Classification of automata and formal languages. Finite state machines, regular languages and their limitations. Tape automata. Pushdown automata and context free languages. Normal form grammars. Turing machines, halting problem, and unsolvability. Computable functions and predicates. Algorithms and effective computability. Recursive functions. Credit units: 3, Prerequisite: CS 201.