l'ÉITIRechercheNouvelles HREF=RépertoiresRessourcesGénie/EngineeringUd'O/UofOSITESearchNewsDirectoriesResourcesSITE

CSI 3104 Introduction to Formal Languages
Winter 2017

(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: CSI2101 or MAT2143.

Course Outline

Professor

Office Hours

Lectures

Textbook

Evaluation

Assignments

Exams

Copyright

Other Links

Course Outline

Details will be filled in as the term progresses.
Topic Reading Lecture Notes Date
Introduction, Languages, Recursive Definitions Chapters 1, 2, 3 Chapters 1 and 2,
Chapter 3
January 9-12
Regular Expressions Chapter 4 Chapter 4 January 12-16
Finite Automata, Transition Graphs Chapters 5, 6 Chapter 5,
Chapter 6
January 16-23
Kleene's Theorem, Nondeterministic Finite Automata Chapter 7 Chapter 7 January 23-February 6
Finite Automata with Output, Regular Languages Chapters 8, 9 Chapter 8,
Chapter 9
February 13-16
Nonregular Languages, Decidability Chapters 10 (pages 187-196), 11 Chapter 10,
Chapter 11
February 16- 
Context-Free Grammars, Grammatical Format Chapters 12, 13    
Pushdown Automata, Context-Free Grammars = Pushdown Automata Chapters 14, 15 (pages 318-327)    
Non-Context-Free Languages, Context-Free Languages Chapters 16, 17    
Decidability, Parsing, Turing Machines Chapters 18 (pages 402-410 and 415-423), 19    
Recursively Enumerable Languages Chapter 23