CSCE 5400 Automata Theory - Fall 2016

Instructor: Paul Tarau, Professor - see my home page for contact info and office hours.

Grader: TBD - see his/her course page here.

Syllabus

• Alphabets, Strings, Languages
• Structural Induction
• Intro to our executable metalanguage: Prolog
• Deterministic Finite Automata
• Nondeterministic Finite Automata
• Regular Expressions
• Applications of Regular Expressions
• Algebraic Laws for Regular Expressions
• Proving Languages Not to Be Regular
• Closure Properties of Regular Languages
• Equivalence and Minimization of Automata
• Chomsky's hierarchy
• Context-Free Grammars
• Normal Forms
• Parsing with Definite Clause Grammars
• Pushdown Automata
• Properties of Context-Free Languages
• Categorial Grammars
• Turing Machines
• Lambda Calculus and Combinatory Logic
• Simply-typed terms, type inference
• Undecidability
• Intractable Problems
• NP-Completeness of the SAT Problem
• Additional NP-Complete Problems
• Complements of Languages in NP
• Problems Solvable in Polynomial Space
• The Complexity of Primality Testing
• The Complexity of Modular-Arithmetic Computations
• Random-Polynomial Primality Testing

Textbook: Introduction to Automata Theory, Languages, and Computation, 3rd ed., by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Pearson Addison Wesley, 2007.

Prerequisites: CSCE 3110 or equivalent

Evaluation:

• 30% midterm exam (open book/internet access allowed)
• 30% final exam (open book/internet access allowed)
• 40% team assignments