Course Description
The purpose of this course is to provide students with a theoretical base in formal language theory for understanding concepts related to programming, automata theory and compilation techniques. The explicit purpose of the course is to illustrate the correspondence between the generation system (grammar) and recognition system (automata). Recognition systems include deterministic and non-deterministic acceptors, process with finite state machines to recognize regular grammar and process with push-down stores, to recognize context-free grammars. Finite automata and regular language present aspects of automata theory (alphabets, languages, transition diagram, deterministic finite automata). Pushdown automata and context-free grammars employs formal language theory as the vehicle for presenting concepts related to the theory of programming languages (syntax analysis LL(k), syntax analysis LR(k). Finally, one give an introduction to Turing’s machine (recognition languages, decidable language, Church-Turing thesis), student should understand limits and capacities of Turing’s machine (therefore a computer) to recognize (or not) a language.
Course ID: CS 422
Credit hours | Theory | Practical | Laboratory | Lecture | Studio | Contact hours | Pre-requisite | 3 | 3 | 3 | MATH 401 |
---|