This course aims to introduce concepts in Automata theory. Based on topics on identifying the different formal language classes, their relationship and diffrences. Students are supposed to design theoretic machines for specific purposes, and prove/disprove properties of these machines.
Course Content
This course contains; Course Info, Introduction to Finite State Automata ,Deterministic and Nondeterministic Finite State Automata ,Equivalence of deterministic and nondeterministic Automata ,Regular Expression and Equivalence with Non-deterministic Automata ,Algebraic Laws for Regular Expression,Pumping Lemma for Regular Languages and Minimization of finite state automata ,Context Free Grammars ,Context Free Languages ,Parse Trees and Ambiguity of grammar ,Pushdown Automata ,Chomsky Normal Form ,Pumping Lemma for Context Free languages ,Turing Machines ,Basic Calculation with Turing machines.
Dersin Öğrenme Kazanımları
Teaching Methods
Assessment Methods
Identify different classes of languages and design automaton to accept that language
10, 11, 12, 14, 16, 3, 4, 6, 9
A, G
Prove or disprove if the given language is regular, proving equivalence of different automata
10, 11, 12, 14, 16, 3, 4, 6, 9
A, G
Represent a given language by a context-free grammar, removing ambiguity, and simplification of a given grammar.
Course Info, Introduction to Finite State Automata
Textbook Chapter 1
2
Deterministic and Nondeterministic Finite State Automata
Textbook Chapter 2.1-2.3
3
Equivalence of deterministic and nondeterministic Automata
Textbook Chapter 2.3
4
Regular Expression and Equivalence with Non-deterministic Automata
Textbook Chapter 3
5
Algebraic Laws for Regular Expression
Textbook Chapter 4.2
6
Pumping Lemma for Regular Languages and Minimization of finite state automata
Textbook Chapter 4.1
7
Context Free Grammars
Textbook Chapter 5.1
8
Context Free Languages
Textbook Chapter 5.1, 5.4
9
Parse Trees and Ambiguity of grammar
Textbook Chapter 5.4
10
Pushdown Automata
Textbook Chapter 6
11
Chomsky Normal Form
Textbook Chapter 7.1
12
Pumping Lemma for Context Free languages
Textbook Chapter 7.2
13
Turing Machines
Textbook Chapter 8.1
14
Basic Calculation with Turing machines
Textbook Chapter 8.1,8.2
Resources
Lecture notes will be supplied by instructor but following textbooks could be used as supplementary materials. 1. J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd edition, 2007, Pearson/Addison-Wesley, 2. Theory of Automata By C.J. Martin
Course Contribution to Program Qualifications
Course Contribution to Program Qualifications
No
Program Qualification
Contribution Level
1
2
3
4
5
1
1. An ability to apply knowledge of mathematics, science, and engineering
2
2. An ability to identify, formulate, and solve engineering problems
X
3
3. An ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
X
4
4. An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice
5
5. An ability to design and conduct experiments, as well as to analyze and interpret data
6
6. An ability to function on multidisciplinary teams
X
7
7. An ability to communicate effectively
X
8
8. A recognition of the need for, and an ability to engage in life-long learning
9
9. An understanding of professional and ethical responsibility
10
10. A knowledge of contemporary issues
11
11. The broad education necessary to understand the impact of engineering solutions in a global, economic, environmental, and societal context
Assessment Methods
Contribution Level
Absolute Evaluation
Rate of Midterm Exam to Success
30
Rate of Final Exam to Success
70
Total
100
ECTS / Workload Table
Activities
Number of
Duration(Hour)
Total Workload(Hour)
Course Hours
14
3
42
Guided Problem Solving
0
0
0
Resolution of Homework Problems and Submission as a Report
8
3
24
Term Project
0
0
0
Presentation of Project / Seminar
0
0
0
Quiz
7
6
42
Midterm Exam
6
5
30
General Exam
6
5
30
Performance Task, Maintenance Plan
0
0
0
Total Workload(Hour)
168
Dersin AKTS Kredisi = Toplam İş Yükü (Saat)/30*=(168/30)
6
ECTS of the course: 30 hours of work is counted as 1 ECTS credit.
Detail Informations of the Course
Course Description
Course
Code
Semester
T+P (Hour)
Credit
ECTS
AN INTRODUCTION to FORMAL LANG. and AUTO. THEORY
-
Fall Semester
3+0
3
6
Course Program
Prerequisites Courses
Recommended Elective Courses
Language of Course
English
Course Level
First Cycle (Bachelor's Degree)
Course Type
Required
Course Coordinator
Assist.Prof. Cihan Bilge KAYASANDIK
Name of Lecturer(s)
Assist.Prof. Cihan Bilge KAYASANDIK
Assistant(s)
Aim
This course aims to introduce concepts in Automata theory. Based on topics on identifying the different formal language classes, their relationship and diffrences. Students are supposed to design theoretic machines for specific purposes, and prove/disprove properties of these machines.
Course Content
This course contains; Course Info, Introduction to Finite State Automata ,Deterministic and Nondeterministic Finite State Automata ,Equivalence of deterministic and nondeterministic Automata ,Regular Expression and Equivalence with Non-deterministic Automata ,Algebraic Laws for Regular Expression,Pumping Lemma for Regular Languages and Minimization of finite state automata ,Context Free Grammars ,Context Free Languages ,Parse Trees and Ambiguity of grammar ,Pushdown Automata ,Chomsky Normal Form ,Pumping Lemma for Context Free languages ,Turing Machines ,Basic Calculation with Turing machines.
Dersin Öğrenme Kazanımları
Teaching Methods
Assessment Methods
Identify different classes of languages and design automaton to accept that language
10, 11, 12, 14, 16, 3, 4, 6, 9
A, G
Prove or disprove if the given language is regular, proving equivalence of different automata
10, 11, 12, 14, 16, 3, 4, 6, 9
A, G
Represent a given language by a context-free grammar, removing ambiguity, and simplification of a given grammar.
Course Info, Introduction to Finite State Automata
Textbook Chapter 1
2
Deterministic and Nondeterministic Finite State Automata
Textbook Chapter 2.1-2.3
3
Equivalence of deterministic and nondeterministic Automata
Textbook Chapter 2.3
4
Regular Expression and Equivalence with Non-deterministic Automata
Textbook Chapter 3
5
Algebraic Laws for Regular Expression
Textbook Chapter 4.2
6
Pumping Lemma for Regular Languages and Minimization of finite state automata
Textbook Chapter 4.1
7
Context Free Grammars
Textbook Chapter 5.1
8
Context Free Languages
Textbook Chapter 5.1, 5.4
9
Parse Trees and Ambiguity of grammar
Textbook Chapter 5.4
10
Pushdown Automata
Textbook Chapter 6
11
Chomsky Normal Form
Textbook Chapter 7.1
12
Pumping Lemma for Context Free languages
Textbook Chapter 7.2
13
Turing Machines
Textbook Chapter 8.1
14
Basic Calculation with Turing machines
Textbook Chapter 8.1,8.2
Resources
Lecture notes will be supplied by instructor but following textbooks could be used as supplementary materials. 1. J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd edition, 2007, Pearson/Addison-Wesley, 2. Theory of Automata By C.J. Martin
Course Contribution to Program Qualifications
Course Contribution to Program Qualifications
No
Program Qualification
Contribution Level
1
2
3
4
5
1
1. An ability to apply knowledge of mathematics, science, and engineering
2
2. An ability to identify, formulate, and solve engineering problems
X
3
3. An ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
X
4
4. An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice
5
5. An ability to design and conduct experiments, as well as to analyze and interpret data
6
6. An ability to function on multidisciplinary teams
X
7
7. An ability to communicate effectively
X
8
8. A recognition of the need for, and an ability to engage in life-long learning
9
9. An understanding of professional and ethical responsibility
10
10. A knowledge of contemporary issues
11
11. The broad education necessary to understand the impact of engineering solutions in a global, economic, environmental, and societal context
