DEPARTMENT OF COMPUTER SCIENCE
CS 4100: FORMAL LANGUAGE THEORY
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.
- Languages and Their Representation
- Types of Languages
- Unrestricted Languages
- Context-sensitive Languages
- Context-free Languages
- Regular Languages
- The Formal Notion of a Grammar
- Types of Grammars
- Derivation Trees
- Recognition Devices
- Turing Machines
- Linear Bounded Automata
- Pushdown Automata
- Finite Automata
Regular homework assignments will be given throughout the course.
Student Learning Outcomes
- I can specify regular expressions for matching strings in a language.
- I can show the equivalence between regular expressions, NFAs, and DFAs.
- I can determine the language recognized by a given FSA.
- I can construct a FSA for a given regular language or regular expression.
- I can construct a derivation tree for a given context-free grammar.
- I can construct a PDA for a given context-free grammars.
- I can prove or disprove closure properties of certain languages.
- I can explain the application of the pumping lemma.
- I can build Turing machines for simple computable functions.
- I can explain the difference between recursively enumerable and recursive languages.