Faculty of Engineering and Natural Sciences · Computer Engineering · Undergraduate
Course Objective
It is aimed to have the most basic knowledge in the classification and definition of languages and to develop programming skills by learning the types and functioning of automata.
Course Content
Introduction to Finite State Automata, Relations between languages and Finite State Automata, Regular languages and Regular expressions,Regular grammars, Ambiguity in grammars, Normal forms (Chomsky Normal form, Greibach Normal form), Stack structured automata, Stack structured automata for context-free grammars, Properties of context-free languages, Turing machines.
Required Resources
Ünal Yarımağan, Özdevinirler (Otomatlar) Kuramı ve Biçimsel Diller, Bıçaklar Kitabevi, 2003.
Recommended Resources
Peter Linz, An Introduction to Formal Languages and Automata, Third Ed., Jones and Bartlett, 2001.
Rules
Remarks and Rules
- Attendance: According to the regulations, if a student does not attend 30% of the total course hours, he/she is absent from the course (DZ) and fails.
2- Plagiarism: You are not allowed to directly copy and paste codes without understanding them available online for your project or homework. If you understood and used the online material, then you must provide and reference to the website or resource that you have used. Otherwise, it will be considered plagiarism and no marks will be given to you.
Course Learning Outcomes
- Uses multiple automata or grammars to represent a complex system.
- Identify abstract machine models and formal languages.
- Explains the definitions of formal languages, language classes (regular, context-free, etc.), and the Chomsky hierarchy.
- Designs finite state machines (DFA/NFA), pushdown automata, and Turing machines.
- Designs an automaton that uses proper language and proper grammar structure.
- Defines a non-regular language using a Push-Down Automata
Core Area Distribution
Teaching Methods
Assessment & Evaluation
ECTS / Workload
| Activity | Quantity | Duration (h) | Total Workload |
|---|---|---|---|
| Course Duration (Including Exam Week) | 15 | 3 | 45 |
| Out of Class Study Period | 15 | 5 | 75 |
| Midterm | 1 | 2 | 2 |
| Quiz | 0 | 0 | 0 |
| Assignment | 0 | 0 | 0 |
| Practice | 0 | 0 | 0 |
| Final | 1 | 2 | 2 |
Course Schedule
| Week | Subject | Preparation |
|---|---|---|
| 1 | Concept of Formal Language, Concept of Automata Theory Introduction to Computation Theory (Sets, Functions, Relations, Graphs, Trees and Proof Methods) | Slides |
| 2 | Languages | Slides |
| 3 | Finite Automata | Slides |
| 4 | Finite Automata (continous) | Slides |
| 5 | Regular Sets and Regular Expressions | Slides |
| 6 | Grammar, Languages and Properties of the Regular Languages | Slides |
| 7 | Midterm | Midterm |
| 8 | Context-Free Languages and Grammars | Slayt |
| 9 | Simplifying Context-Free Grammars | Slides |
| 10 | Chomsky and Greibach Normal Forms | Slides |
| 11 | Chomsky and Greibach Normal Forms (Continuous) | Slides |
| 12 | Pushdown Automata | Slides |
| 13 | Pushdown Automata (Continues) | Slides |
| 14 | Turing Machines | Slides |
| 15 | Turing Machine models | Slides |
| 16 | Final Exam | Final Exam |