CSI 3104

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
CSI 3104

CSI 3104 Introduction to Formal Languages
Winter 2003

(3 hours of lecture per week, 3 credits)
Regular languages, finite automata, transition graphs, Kleene's theorem. Finite automata with output. Context-free languages, derivation trees, normal form grammars, pumping lemma, pushdown automata, determinism. Decidability. Recursively enumerable languages, Turing machines, the halting problem. Prerequisites: MAT1361, MAT2343 or MAT2143.

Professor

Textbook

Introduction to Computer Theory

Approximate Course Outline:

January 7-10, Introduction, Langages, Recursive Definitions, Chapters 1, 2, 3
January 14, Regular Expressions, Chapter 4
January 17, Problem Session
January 21-24, Finite Automata, Transition Graphs, Chapters 5, 6
January 28-February 4, Kleene's Theorem, Nondeterministic Finite Automata, Chapter 7
February 7, Term Test 1
February 11-14, Finite Automata with Output, Regular Languages, Chapters 8,9
February 17-21, Study Break
February 25-28, Nonregular Languages, Decidability, Chapters 10 (pages 187-196), 11
March 4-7, Context-Free Grammars, Grammatical Format, Chapters 12, 13
March 11, Chapter 13 continued
March 14, Term Test 2
March 18-21, Pushdown Automata, Context-Free Grammars = Pushdown Automata, Chapters 14, 15 (pages 318-327)
March 25-28, Non-Context-Free Languages, Context-Free Languages, Chapters 16, 17
April 1-4, Decidability, Parsing, Turing Machines, Chapters 18 (pages 402-410 and 415-423), 19
April 8, Recursively Enumerable Languages, Review, Chapter 23