Course Information


Course Information
Course Title Code Semester L+U Hour Credits ECTS
FORMAL LANGUAGES AND AUTOMATA THEORIES YZM207 3. Semester 3 + 0 3.0 4.0

Prerequisites None

Language of Instruction Turkish
Course Level Bachelor's Degree
Course Type Compulsory
Mode of delivery
Course Coordinator
Instructors Savaş TAKAN
Assistants
Goals The objectives of this course are not only to introduce students to the mathematical foundations of computation including automata theory and the theory of formal languages and grammars; but also to provide students with an understanding of such basic concepts as automata, the equivalent regular expressions, the equivalence of languages described by automata, regular expressions, pushdown automata, the equivalent context free grammars, the equivalence of languages described by pushdown automata, context free grammars, Turing machines and the equivalence of languages described by Turing machines.
Course Content Mathematical Tools (Definitions, Theorems, and Proofs); Types of Proofs; Regular Languages; Finite Automata; Nondeterminism; Regular Expressions; Nonregular Languages; Context-Free Languages; Context-free Grammars; Pushdown Automata; Non-context-free Languages; Turing Machines; Variants of Turing Machines; Definition of "Algorithm"; Decidability; Decidable Languages; Reducibility; NP-completeness; Reducibility; Recognizability
Learning Outcomes 1) Students will be able to analyze finite automata, deterministic and non-deterministic automata, regular expressions, pushdown automata, Turing machines, formal languages, and grammars
2) Students will be able to design finite automata, deterministic and non-deterministic automata, regular expressions, pushdown automata, Turing machines, formal languages, and grammars
3) Students will be familiar with Turing Machines and Problem Classes.
4) Students will improve problem solving skills.

Weekly Topics (Content)
Week Topics Teaching and Learning Methods and Techniques Study Materials
1. Week Course overview, formation of preliminary concepts, mathematical tools, definitions, theorems, and proofs, types of proofs Lecture
Opinion Pool
 Presentation (Including Preparation Time)
2. Week Deterministic finite automata (DFA) Lecture
Opinion Pool
 Presentation (Including Preparation Time)
3. Week Non-deterministic finite automata (NFA) Lecture
Opinion Pool
 Presentation (Including Preparation Time)
4. Week Equivalence of DFA and NFA, and regular expressions Lecture
Opinion Pool
 Presentation (Including Preparation Time)
5. Week Epsilon transition, pumping Lemma, pigeonhole principle, and closure properties Lecture
Opinion Pool
 Presentation (Including Preparation Time)
6. Week Optimal DFA, and overview Lecture
Opinion Pool
 Presentation (Including Preparation Time)
7. Week Context-free languages, context-free grammars, parse tree, ambiguity, closure properties Lecture
Opinion Pool
 Presentation (Including Preparation Time)
8. Week Preparation, problem solving Problem Solving
Opinion Pool
 Presentation (Including Preparation Time)
9. Week Pushdown automata (PDA) Lecture
Opinion Pool
 Presentation (Including Preparation Time)
10. Week Overview of context-free grammars, and Church-Turing hypothesis Lecture
Opinion Pool
 Presentation (Including Preparation Time)
11. Week Turing Machines, Recognition and Computation, Church-Turing Hypothesis Lecture
Opinion Pool
 Presentation (Including Preparation Time)
12. Week NP-completeness, decidability, reducibility, and recognizability Lecture
Opinion Pool
 Presentation (Including Preparation Time)
13. Week An overview Lecture
Opinion Pool
 Presentation (Including Preparation Time)
14. Week An overview Problem Solving
Opinion Pool
 Presentation (Including Preparation Time)

Sources Used in This Course
Recommended Sources
Daniel I. A. Cohen, Introduction to Computer Theory, Prentice-Hall, 2nd Edition, 1997
Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, 3rd Edition, 2012

Relations with Education Attainment Program Course Competencies
Program RequirementsContribution LevelDK1DK2DK3DK4
PY155555
PY255555
PY352222
PY454444

*DK = Course's Contrubution.
0 1 2 3 4 5
Level of contribution None Very Low Low Fair High Very High
.

ECTS credits and course workload
Event Quantity Duration (Hour) Total Workload (Hour)
Course Duration (Total weeks*Hours per week) 14 2.3
Work Hour outside Classroom (Preparation, strengthening) 14 2.3
Homework 5 2
Presentation (Including Preparation Time) 36 1
Midterm Exam 1 2
Time to prepare for Midterm Exam 1 8
Final Exam 1 2
Time to prepare for Final Exam 1 8
Total Workload
Total Workload / 30 (s)
ECTS Credit of the Course
Quick Access Hızlı Erişim Genişlet
Course Information
  • Course Information
  • Weekly Topics (Content)
  • Sources Used in This Course
  • Relations with Education Attainment Program Course Competencies
  • ECTS credits and course workload