Information
Code | MT557 |
Name | Finite Automata and Languages |
Term | 2024-2025 Academic Year |
Semester | . Semester |
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 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 |