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

Professor

Office Hours

Lectures

Textbook

Evaluation

Assignments

Exams

Copyright

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- 
Finite Automata, Transition Graphs Chapters 5, 6  
Kleene's Theorem, Nondeterministic Finite Automata Chapter 7  
Finite Automata with Output, Regular Languages Chapters 8, 9  
Nonregular Languages, Decidability Chapters 10 (pages 187-196), 11  
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