| School/Faculty/Institute |
Faculty of Engineering |
| Course Code |
MATH 321 |
| Course Title in English |
Automata Theory and Formal Language |
| Course Title in Turkish |
Biçimsel Diller ve Otomatlar Kuramı |
| Language of Instruction |
EN |
| Type of Course |
Flipped Classroom |
| Level of Course |
Introductory |
| Semester |
Fall |
| Contact Hours per Week |
| Lecture: 3 |
Recitation: none |
Lab: none |
Other: none |
|
| Estimated Student Workload |
160 hours per semester |
| Number of Credits |
6 ECTS |
| Grading Mode |
Standard Letter Grade
|
| Pre-requisites |
None |
| Expected Prior Knowledge |
Basic Discrete Mathematics and Data Structures Knowledge |
| Co-requisites |
None |
| Registration Restrictions |
Only Undergraduate Students |
| Overall Educational Objective |
To learn the fundamentals of theory of computation, basic graph theory and introductory discrete mathematics, learn the classification between classes of languages (regular, context-free, and more) and design grammars and machines that will generate/recognize these languages. |
| Course Description |
This course covers the fundamentals of theory of computation: basic graph theory, introductory discrete mathematics, regular languages, finite state machines, push-down automata, regular expressions, context-free grammars, Turing machines, decidability, reducibility, time complexity |
| Course Description in Turkish |
Bu derste, biçimsel diller ve otomatlar kuramının temel kavramları şu başlıklar altında işlenmektedir: temel çizge teorisi, sonlu küme matematiğine giriş, düzenli diller, sonlu durum makineleri, ters otomat, düzenli ifadeler, bağlama duyarsız gramerler, Turing makineleri, karar verilebilirlik, indirgenebilirlik, zaman karmaşıklığı |
Course Learning Outcomes and Competences
Upon successful completion of the course, the learner is expected to be able to:
1) know basic discrete mathematics and graph theory
2) identify finite state machines, regular languages, regular expressions, determinism and nondeterminism and their connection
3) know context-free languages, push-down automata and their connection
4) comprehend Turing machines, decidability and reducibility
5) apply new knowledge as needed, using appropriate learning strategies
|
| Program Learning Outcomes/Course Learning Outcomes |
1 |
2 |
3 |
4 |
5 |
| 1) An ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics |
|
|
|
|
|
| 2) An ability to apply engineering design to produce solutions that meet specified needs with consideration of public health, safety, and welfare, as well as global, cultural, social, environmental, and economic factors |
|
|
|
|
|
| 3) An ability to communicate effectively with a range of audiences |
|
|
|
|
|
| 4) An ability to recognize ethical and professional responsibilities in engineering situations and make informed judgments, which must consider the impact of engineering solutions in global, economic, environmental, and societal contexts |
|
|
|
|
|
| 5) An ability to function effectively on a team whose members together provide leadership, create a collaborative and inclusive environment, establish goals, plan tasks, and meet objectives |
|
|
|
|
|
| 6) An ability to develop and conduct appropriate experimentation, analyze and interpret data, and use engineering judgment to draw conclusions |
|
|
|
|
|
| 7) An ability to acquire and apply new knowledge as needed, using appropriate learning strategies. |
|
|
|
|
|
Relation to Program Outcomes and Competences
| N None |
S Supportive |
H Highly Related |
| |
|
|
| |
Program Outcomes and Competences |
Level |
Assessed by |
| 1) |
An ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics |
H |
Exam,HW
|
| 2) |
An ability to apply engineering design to produce solutions that meet specified needs with consideration of public health, safety, and welfare, as well as global, cultural, social, environmental, and economic factors |
N |
|
| 3) |
An ability to communicate effectively with a range of audiences |
N |
|
| 4) |
An ability to recognize ethical and professional responsibilities in engineering situations and make informed judgments, which must consider the impact of engineering solutions in global, economic, environmental, and societal contexts |
N |
|
| 5) |
An ability to function effectively on a team whose members together provide leadership, create a collaborative and inclusive environment, establish goals, plan tasks, and meet objectives |
N |
|
| 6) |
An ability to develop and conduct appropriate experimentation, analyze and interpret data, and use engineering judgment to draw conclusions |
N |
|
| 7) |
An ability to acquire and apply new knowledge as needed, using appropriate learning strategies. |
S |
HW
|
| Prepared by and Date |
ŞENİZ DEMİR , November 2023 |
| Course Coordinator |
ŞENİZ DEMİR |
| Semester |
Fall |
| Name of Instructor |
Assoc. Prof. Dr. ŞENİZ DEMİR |
Course Contents
| Week |
Subject |
| 1) |
Basic Discrete Mathematics and Graph Theory |
| 2) |
Basic Discrete Mathematics and Graph Theory |
| 3) |
Finite State Machines and Regular Languages |
| 4) |
Finite State Machines and Regular Languages |
| 5) |
Nondeterminism and Regular Expressions |
| 6) |
Equivalence of Regular Expressions and Finite State Machines |
| 7) |
Nonregular Languages and Pumping Lemma |
| 8) |
Nonregular Languages and Pumping Lemma |
| 9) |
Context-Free Grammars and Ambiguity |
| 10) |
Push-Down Automata |
| 11) |
Non-Context-Free Languages and Pumping Lemma |
| 12) |
Turing Machines |
| 13) |
Turing Machines |
| 14) |
Advanced Topics (Decidability, reducibility, time complexity) |
| 15) |
Final Exam/Project/Presentation |
| 16) |
Final Exam/Project/Presentation |
| Required/Recommended Readings | Introduction To The Theory Of Computation – Michael Sipser 3rd ed. |
| Teaching Methods | Flipped classroom. In-class flipped practices. |
| Homework and Projects | In-class flipped practices. No Project. |
| Laboratory Work | None |
| Computer Use | For in-class practices |
| Other Activities | None |
| Assessment Methods |
| Assessment Tools |
Count |
Weight |
| Quiz(zes) |
3 |
% 10 |
| Homework Assignments |
3 |
% 10 |
| Midterm(s) |
2 |
% 80 |
| TOTAL |
% 100 |
|
| Course Administration |
demirse@mef.edu.tr
536
Instructor’s office: Room 535 (5th floor)
Office hours: TBA.
E-mail address: demirse@mef.edu.tr
Rules for attendance: No attendance required.
Missing an in-class practice: Provided that proper documents of excuse are presented, a
make-up will be given to each missed practice.
Missing a midterm: Provided that proper documents of excuse are presented, make-up for
missed midterms will be given.
Missing a final: No final exam.
A reminder of proper classroom behavior, code |
Information Package / Course Catalogue