| Course Type | Elective Course |
|---|
| Course Level | Bachelor's Degree |
|---|
| Year of Study | - |
|---|
| Semester | - |
|---|
| ECTS | 5 |
|---|
| Name of Lecturer(s) |
|
| Learning Outcomes |
At the end of this course, the students;
- Learn basic concepts and models of Automata Theory, Computation and Formal languages.
- Be able to solve problems on abstract machines such as Finite state automata, Pushdown automata and Turing machines.
- Learn about the representations of formal languages using regular expressions and formal grammars.
- Understand abstract models of the computational process and discuss about the limits and power of these models.
|
| Mode of Delivery | Face to face |
|---|
| Prerequisites | No |
|---|
| Recommended Optional Programme Components | None |
|---|
| Course Description | Introduction to Automata Theory. Basic mathematical concepts and methods. Symbols, Alphabets, Strings, Languages, Problems. Deterministic finite automata. Nondeterministic finite automata. Regular languages and expressions. Kleene's theorem. Formal grammars. Context-free languages. Pushdown automata. Turing machines. Computability and Decidability. Halting problem, Unsolvable problems. Computational complexity: P and NP classes. |
|---|
| Course Contents |
| WEEK |
TOPICS |
|
1st Week |
Introduction to Automata Theory. |
|
2nd Week |
Basic mathematical concepts and methods. |
|
3rd Week |
Symbols, Alphabets, Strings, Languages, Problems. |
|
4th Week |
Deterministic finite automata. |
|
5th Week |
Nondeterministic finite automata. |
|
6th Week |
Regular languages and expressions. |
|
7th Week |
Kleene's theorem. |
|
8th Week |
Mid-term |
|
9th Week |
Formal grammars. |
|
10th Week |
Context-free languages. |
|
11th Week |
Pushdown automata. Turing machines. |
|
12th Week |
Computability and Decidability. |
|
13th Week |
Halting problem, Unsolvable problems. |
|
14th Week |
Computational complexity: P and NP classes. |
|
15th Week |
General Repeat. |
|
| Recommended or Required Reading | 1. Hopcroft J.E., Motwani R., Ullman J.D., Introduction to Automata Theory, Languages and Computation, 3/E, Addison Wesley, 2006
2. Kelley D., Automata and Formal Languages, Prentice Hall, 1995
3. Sipser M., Introduction to the Theory of Computation, 2/E, Thomson / Course Technology, 2005
|
|---|
| Planned Learning Activities and Teaching Methods |
- Lecture
- Questions/Answers
- Presentation
- Report Preparation
- Project
- Experiment
- Problem Solving
- Practice
|
|---|
| Assessment Methods and Criteria |
|
Quantity |
Percentage (%) |
| Mid-term |
1 |
30 |
| Assignment |
8 |
10 |
| Quiz |
4 |
20 |
| Total(%) |
|
60 |
| Contribution of In-term Studies to Overall Grade(%) |
|
60 |
| Contribution of Final Examination to Overall Grade(%) |
|
40 |
| Total(%) |
|
100 |
|
| ECTS Allocated Based on Student Workload |
| Activities |
Quantity |
Duration (Hour) |
Total Workload (Hour) |
| Midterm exam |
1 |
1.5 |
1.5 |
| Preparation for Quiz |
|
|
|
| Individual or group work |
|
|
|
| Preparation for Final exam |
1 |
20 |
20 |
| Course hours |
14 |
3 |
42 |
| Preparation for Midterm exam |
1 |
15 |
15 |
| Laboratory (including preparation) |
|
|
|
| Final exam |
1 |
1.5 |
1.5 |
| Homework |
|
|
|
| Project |
1 |
70 |
70 |
| Quiz |
4 |
0.5 |
2 |
| Total Work Load | 152 |
| Total Work Load / 30 (h) | 5.06 |
| ECTS Credit of the Course | 5 |
|
| Language of Instruction | Turkish |
|---|
| Work Placement(s) | No |
|---|
