Course Description

Various types of languages (context-sensitive, context-free, regular). Discussion of recognition devices such as pushdown automata, linear bounded automata, and Turing machines. Some topics of current interest. Prerequisite: MATH 2220 or MATH 3220.

Course Syllabus

1. Languages and Their Representation
2. Types of Languages
   1. Unrestricted Languages
   2. Context-sensitive Languages
   3. Context-free Languages
   4. Regular Languages
3. Grammars
   1. The Formal Notion of a Grammar
   2. Types of Grammars
   3. Recursiveness
   4. Derivation Trees
4. Recognition Devices
   1. Turing Machines
   2. Linear Bounded Automata
   3. Pushdown Automata
   4. Finite Automata

Course Requirements