CS8813: Formal Languages and Automata Theory
- Background Information
- Basic proof concepts, induction, recursive construction
- Definitions of Languages, and how problems can be expressed
in terms of defining Languages.
- Finite Automata and Regular Expressions
- Equivalence proofs for Deterministic, Non-Deterministic
Finite Automata and Regular Expressions
- Definitions of Regular Languages
- Constructions for translating between different descriptions of Regular Languages.
- Properties of Regular Languages including closure under operations such as concatenation, union, etc.
- Minimization of automata transition functions.
- Context-Free Grammars and Languages
- Definition of grammars through production rules
- Parse Tree's and application to parsers
- Ambiguity in grammars and languages
- Identification of inherently ambiguious languages
- Definition of Pushdown Automata and proofs of equivalence to Context-Free Grammars.
- Proofs of distinctions between Regular Languages and Context-Free Grammars and languages defined by deterministic push-down automta.
- Proofs about Simplifying Context-Free Grammars: THe Chomsky Normal Form and Greibach Normal Form
- Techniques for Proving Languages are/are not described by context-free grammars.
- Proofs about closure properties of Context-Free Grammars under various operations (complement, union, intersection, etc.)
- Turing Machines
- The Halting Problem.
- Equivalences of deterministic and non-deterministic Turing Machines
- Equivalences of certian restricted forms of Turing Machines
- Relationship between a turing machine and a modern computer architecture
- Undecidability (Languages for which the turing machine cannot be guaranteed to terminate on failure.)
- Languages not recognized by Turing machines.
-
diagonalization language
- Languages that are recognized by Turing machines but are undecidable.
- The Universal Turing Machine and the Universal Language
- Undecidability of the Universal Language
- Post's Correspondence Problem and other examples of undecidability
- Intractable Problems (Languages for which cannot be recognized efficiently)
- Problems in the class of Deterministic and Non-Deterministic Polynomial time.
- Polynonial-Time Reductions as a technique for proving that a problem is intractable.
- NP-Complete Problems
- The Satisfiability Problem
luke@cs.msstate.edu
Last modified: Mon Aug 20 11:14:23 CDT 2001