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

CSI 3104 Introduction to Formal Languages
Winter 2019

(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


Office Hours







Other Links

Course Outline

Details will be filled in as the term progresses.
Topic Reading Date
Introduction, Languages, Recursive Definitions Chapters 1, 2, 3 January 7-10
Regular Expressions Chapter 4 January 10-21
Finite Automata, Transition Graphs Chapters 5, 6 January 21-28
Kleene's Theorem, Nondeterministic Finite Automata Chapter 7 January 28-February 14
Finite Automata with Output, Regular Languages Chapters 8, 9 February 14-25
Nonregular Languages, Decidability Chapters 10 (pages 187-196), 11 February 25-March 7
Context-Free Grammars, Grammatical Format Chapters 12, 13 March 7- 
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