Syllabus Application
Formal Languages and Automata Theory
CS 302
Faculty:
Faculty of Engineering and Natural Sciences
Semester:
Fall 2025-2026
Course:
Formal Languages and Automata Theory - CS 302
Classroom:
FASS-1050,FASS-G018
Level of course:
Undergraduate
Course Credits:
SU Credit:3.000, ECTS:6, Basic:2, Engineering:4
Prerequisites:
-
Corequisites:
CS 302R
Course Type:
Lecture
Course Information
Catalog Course Description
Introduction to languages, grammars and computation, Chomsky hierarchy, Regular languages and regular expressions, finite state automata and nondeterminism, automata determinization and minimization, pumping lemma and closure properties for regular languages, context free languages and grammars, push-down automata, pumping lemma for context-free languages, closure properties of context-free languages.
Course Learning Outcomes:
| 1. | Construct deterministic and nondeterministic finite state automata (DFA and NFA) for solving simple decision problems and perform conversions from nondeterministic to deterministic finite automata as well as between regular expressions and finite state automata. |
|---|---|
| 2. | Evaluate the computational complexity of algorithms involved in the decision problems of finite state automata, use the pumping lemma to demonstrate the non-regularity of languages |
| 3. | Compute the minimal state machine corresponding to a DFA, |
| 4. | Understand and construct context-free grammars (CFG) for formal definitions involving recursion such as regular expressions ; in particular understand the fundamental role played by CFG in designing formal computer languages with simple examples |
| 5. | Construct (infinite state) push down automata as acceptors of context free languages ; in particular compute from CFGs the corresponding push down automaton and vice versa |
| 6. | Use the CFG version of the pumping lemma to prove languages that are not context free |
| 7. | Evaluate the computational complexity of algorithms involved in the decision problems of context free grammars and push down automaton, classify and simplify grammars into their useful canonical forms |
| 8. | Use deterministic push down automata to parse formal language strings (computer programs) by using (i) top down or (ii) bottom up techniques |
| 9. | Formulate simple language manipulation techniques using Turing Machines |
| 10. | In general ,learn and master the use mathematical induction techniques in proving statements on formal language and automata theory |
Course Objective
To introduce finite state machines , contex free grammars and Turing Machines (only on an introductory level) and their properties as the basis for the formal expressivity of computer languages and present algorithms and their computational complexity for solving linguistic decision problems .
-
Course Materials
Resources:
Main Text: Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani
& Ullman, Pearson (Addison Wesley) 2006 , 3rd edition.
Auxiliary Text: Elements of the Theory of Computation, Lewis & Papadimitriou, Prentice Hall
1998.
& Ullman, Pearson (Addison Wesley) 2006 , 3rd edition.
Auxiliary Text: Elements of the Theory of Computation, Lewis & Papadimitriou, Prentice Hall
1998.