Course Code & Number:
Level of Course:
Pre-requisites & Co-requisites:
Mid-terms - 20%
Quizzes and Homeworks - 25%
Projects - 20%
Final - 35%
The objective of this course is to provide an understanding of the theory of automata, computability of problems and complexity of computations. Different models of computation will be introduced and their comparisons will be done.
Deterministic finite automata. Non-deterministic finite automata. Regular expressions. Context free grammars. Push down automata. Turing machine. Decidability and undecidability. P and NP classes. Fundamental problems.
Upon succesful completion of this course, a student will be able to
1. understand the functioning of Finite-State Machines, Deterministic Finite-State Automata, Nondeterministic Finite-State Automata and Pushdown Automata;
2. create Automata to accept strings from various simple languages;
3. understand Formal Grammars;
4. discuss the difference between Regular, Context-Free and Context-Sensitive languages;
5. give grammars to produce strings from specific languages.