University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Course Page
Computer Science 456/656
Automata and Formal Languages
Fall 2010
Syllabus
-
Deep questions.
-
Can you "know" pi?
-
Can anything be bigger than infinity?
-
Can all truth be discovered by reason?
-
Alphabets, strings, and languages (page 13)
-
Regular languages and finite automata.
-
Finite automata (1.1, 1.2).
-
Regular languages and regular expressions (1.3).
-
The pumping lemma (1.4).
-
Context-free languages
-
Context-free grammars (2.1).
-
Context-free grammars for algebraic languages.
-
LALR parsing.
-
Push-down automata (2.2).
-
The other pumping lemma (2.3).
-
Computability and Decidability.
-
Turing machines (3.1, 3.2, 3.3).
-
The halting problem and other undecidable problems (4.1, 4.2).
-
Complexity theory.
-
The polynomial class P-TIME (7.2).
-
NP-completeness (7.4).
-
Parallel computation and Nick Pippenger's class (10.5).