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

CSI 3104 Introduction to Formal Languages
Winter 2020

(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

Details will be filled in as the term progresses.
Topic Reading
Introduction, Languages, Recursive Definitions Chapters 1, 2, 3
Regular Expressions Chapter 4
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