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 |
| Activities |
Number |
Weight (%) |
| Course Attendance/Participation |
- |
- |
| Laboratory |
- |
- |
| Application |
- |
- |
| Homework |
3 |
20% |
| Project |
- |
- |
| Presentation |
- |
- |
| Field Work |
- |
- |
| Internship |
- |
- |
| Course Boards |
- |
- |
| Quiz |
5 |
10% |
| Midterm Exam |
1 |
35% |
| Final Exam |
1 |
35% |
|
Total |
100% |
| Tentative ECTS-Workload Table |
| Activities |
Number/Weeks |
Duration (Hours) |
Workload |
| Course Hours (first 6 weeks) |
6 |
4 |
24 |
| Course Hours (last 6 weeks) |
6 |
3 |
18 |
| Laboratory |
- |
- |
- |
| Application |
- |
- |
- |
| Homework |
3 |
6 |
18 |
| Project |
- |
- |
- |
| Presentation |
- |
- |
- |
| Field Work |
- |
- |
- |
| Internship |
- |
- |
- |
| Course Boards |
- |
- |
- |
| Preparation for Quiz |
5 |
1 |
5 |
| Preparation for Midterm Exam |
1 |
25 |
25 |
| Final Exam |
1 |
2 |
2 |
| Preparation for Final Exam |
1 |
25 |
25 |
| Study Hours Out of Class (preliminary work, reinforcement, etc.) |
12 |
5 |
60 |
| Total Workload | | |
177 |
| Total Workload / 30 | | |
177 / 30 |
| | |
5.900000 |
| ECTS Credits of the Course | | |
6 |
|
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
|
|
|
|
|
|
|
|
|
|
|