TÜRKÇE
ENGLISH
Information
| Code | MT557 |
| Name | Finite Automata and Languages |
| Term | 2022-2023 Academic Year |
| Term | Spring |
| Duration (T+A) | 3-0 (T-A) (17 Week) |
| ECTS | 6 ECTS |
| National Credit | 3 National Credit |
| Teaching Language | Türkçe |
| Level | Yüksek Lisans Dersi |
| Type | Normal |
| Mode of study | Yüz Yüze Öğretim |
| Catalog Information Coordinator | Doç. Dr. DİLEK KAHYALAR |
| Course Instructor |
1 |
Course Goal / Objective
The aim of this course is to make students understand basic properties of semigroup and monoids, transformation monoids, free semigroups and monoids, finite automata, incomplete and non-deterministic automata , rational sets and Kleene theorem, the syntactic congruence, the minimal automaton, reduced automata, the transformation monoid of an automato, the calculation of the syntactic monoid , regular and rational languages, context-free languages, Chomsky Normal Form, pushdown automata.
Course Content
In this course basic properties of semigroup and monoids, transformation monoids, free semigroups and monoids, finite automata, incomplete and non-deterministic automata , rational sets and Kleene theorem, the syntactic congruence, the minimal automaton, reduced automata, the transformation monoid of an automato, the calculation of the syntactic monoid , regular and rational languages, context-free languages, Chomsky Normal Form, pushdown automata are described.
Course Precondition
NONE
Resources
Automata and Languages, J.M Howie, Clarendon Press.
Notes
Lecture Notes
Course Learning Outcomes
| Order | Course Learning Outcomes |
|---|---|
| LO01 | Recognizes basic properties of semigroups and monoids. |
| LO02 | Recognizes transformation monoids, free semigroups and monoids |
| LO03 | Recognizes finite automata. |
| LO04 | Recognizes incomplete and non-deterministic automata. |
| LO05 | Realizes rational sets and Kleene theorem. |
| LO06 | Recognizes the syntactic congruence. |
| LO07 | Realizes the minimal automaton. |
| LO08 | Realizes reduced automata |
| LO09 | Recognizes the transformation monoid of an automato. |
| LO10 | Realizes the calculation of the syntactic monoid. |
| LO11 | Recognizes regular and rational languages. |
| LO12 | Recognizes context-free languages. |
| LO13 | Realizes Chomsky Normal Form. |
| LO14 | Realizes pushdown automata. |
Relation with Program Learning Outcome
| Order | Type | Program Learning Outcomes | Level |
|---|---|---|---|
| PLO01 | Bilgi - Kuramsal, Olgusal | Knows in detail the relationship between the results in her area of expertise and other areas of mathematics. | 4 |
| PLO02 | Bilgi - Kuramsal, Olgusal | Knows in detail the relationship between the results in his area of expertise and other areas of mathematics. | 4 |
| PLO03 | Bilgi - Kuramsal, Olgusal | Establishes new mathematical models with the help of the knowledge gained in the field of specialization. | 5 |
| PLO04 | Bilgi - Kuramsal, Olgusal | Has basic knowledge in all areas of mathematics. | 4 |
| PLO05 | Bilgi - Kuramsal, Olgusal | It presents the knowledge gained in different fields of mathematics and their relations with each other in the simplest and most understandable way. | 5 |
| PLO06 | Bilgi - Kuramsal, Olgusal | Effectively uses the technical equipment needed to express mathematics. | |
| PLO07 | Bilgi - Kuramsal, Olgusal | poses original problems related to field and presents different solution techniques. | 4 |
| PLO08 | Bilgi - Kuramsal, Olgusal | carries out original and qualified scientific studies on the subject related to its field. | 5 |
| PLO09 | Bilgi - Kuramsal, Olgusal | Analyzes existing mathematical theories and develops new theories. | |
| PLO10 | Beceriler - Bilişsel, Uygulamalı | Knows the teaching-learning techniques in areas of mathematics that require expertise and uses these techniques effectively at every stage of education. | 3 |
| PLO11 | Yetkinlikler - Bağımsız Çalışabilme ve Sorumluluk Alabilme Yetkinliği | To have knowledge of a foreign language at a level to be able to follow foreign sources related to the field and to communicate verbally and in writing with foreign stakeholders. | 4 |
| PLO12 | Yetkinlikler - Bağımsız Çalışabilme ve Sorumluluk Alabilme Yetkinliği | presents and publishes its original works within the framework of scientific ethical rules for the benefit of its stakeholders. | 5 |
| PLO13 | Yetkinlikler - Öğrenme Yetkinliği | Adheres to the ethical rules required by its scientific title | 5 |
Week Plan
| Week | Topic | Preparation | Methods |
|---|---|---|---|
| 1 | Basic properties of semigroups and monoids | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 2 | Transformation monoids, free semigroups and monoids | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 3 | Finite automata | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 4 | Incomplete and non-deterministic automata | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 5 | Rational sets and Kleene theorem | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 6 | The syntactic congruence | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 7 | The minimal automaton | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 8 | Mid-Term Exam | Exam | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 9 | The transformation monoid of an automato | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 10 | The calculation of the syntactic monoid | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 11 | Regular and rational languages | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 12 | Context-free languages | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 13 | Chomsky Normal Form | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 14 | Pushdown automata | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 15 | Related exercises | Prepare the releated topics | Öğretim Yöntemleri: Anlatım, Soru-Cevap |
| 16 | Term Exams | Term Exam | Ölçme Yöntemleri: Yazılı Sınav |
| 17 | Term Exams | Term Exam | Ölçme Yöntemleri: Yazılı Sınav |
Student Workload - ECTS
| Works | Number | Time (Hour) | Workload (Hour) |
|---|---|---|---|
| Course Related Works | |||
| Class Time (Exam weeks are excluded) | 14 | 3 | 42 |
| Out of Class Study (Preliminary Work, Practice) | 14 | 5 | 70 |
| Assesment Related Works | |||
| Homeworks, Projects, Others | 0 | 0 | 0 |
| Mid-term Exams (Written, Oral, etc.) | 1 | 15 | 15 |
| Final Exam | 1 | 30 | 30 |
| Total Workload (Hour) | 157 | ||
| Total Workload / 25 (h) | 6,28 | ||
| ECTS | 6 ECTS | ||