MT557 Finite Automata and Languages

6 ECTS - 3-0 Duration (T+A)- . Semester- 3 National Credit

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

Update Time: 09.05.2024 11:37