Course Description:An introduction to automata theory, computability, and formal languages.
- C or higher in CS 3358: Data Structures
|[knowledge and skill] What are FSMs and FSRs? How can they be used to model hardware and software systems?|
|[knowledge] Chomsky hierarchy. FSM/RE/RL. PDL/CFL. LBA/CSL. TM/PSL. Unsolvable; e.g., halting problem. BNF for R/CF/CS/PS grammars.|
|[knowledge and skill] Algorithm development, Trichotomy and Dichotomy Axioms. Hierarchy of operators. Postfix notation and conversion from infix. Etc.|
Lecture/Lab Hours: 3 hours lecture, 0 hours lab
Offered: Frequently (typically both Fall and Spring).