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