School of Engineering \ Computer Engineering
Course Credit
ECTS Credit
Course Type
Instructional Language
Programs that can take the course
This course presents the basic concepts and proof techniques in automata theory. Topics covered include the following: DFA, NFA, properties of regular languages, regular expressions, the pumping lemma for regular languages, context-free grammars, Chomsky normal form, PDA, Turing machines, undecidability, NP-completeness.
Textbook and / or References
Introduction to the Theory of Computation. By Michael Sipser.
Basic understanding of formal models of computation.
Understanding and writing regular expressions and context-free grammars.
Understanding TMs, reduction proofs, and inherent limitations of computation.
1. Designing and understanding DFAs and NFAs
2. Writing regular expressions
3. Proving that a language is non-regular
4. Designing and understanding CFGs and PDAs
5. Simplifying a grammar into CNF
6. Learning the Turing machines, and the reduction proof technique
Week 1: DFA
Week 2: NFA
Week 3: Regular expressions
Week 4: Pumping lemma
Week 5: Context-free grammars
Week 6: Context-free grammars
Week 7: Ambiguity, CNF
Week 8: PDA
Week 9: Turing machines
Week 10: Undecidability
Week 11: Complexity theory
Week 12: NP-completeness
Tentative Assesment Methods
Midterm 35 %
Final 35 %
Quiz 10 %
Homework 20 %
|
Program Outcome
*
|
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
Course Outcome
|
|---|
| 1 |
C
|
|
|
|
|
|
|
|
|
|
|
| 2 |
C
|
|
|
|
|
|
|
|
|
|
|
| 3 |
C, D
|
|
|
|
|
|
|
|
|
|
|
| 4 |
C
|
|
|
|
|
|
|
|
|
|
|
| 5 |
C
|
|
|
|
|
|
|
|
|
|
|
| 6 |
C
|
|
|
|
|
|
|
|
|
|
|