Faculty of Engineering and Natural Sciences · Software Engineering (English 30%) · Undergraduate
ECTS: 5 T+P+L: 2+0+1 Departmental Elective
Coordinator: Dr. Öğr. Üyesi Şengül BAYRAK
Instructors: Dr. Öğr. Üyesi Şengül BAYRAK
Course Objective
It is aimed to have the most basic knowledge in the classification and definition of languages and to develop programming skills by learning the types and functioning of automata.
Course Content
Introduction to Finite State Automata, Relations between languages and Finite State Automata, Regular languages and Regular expressions,Regular grammars, Ambiguity in grammars, Normal forms (Chomsky Normal form, Greibach Normal form), Stack structured automata, Stack structured automata for context-free grammars, Properties of context-free languages, Turing machines.
Course Learning Outcomes
- Uses multiple automata or grammars to represent a complex system.
- Identify abstract machine models and formal languages.
- Explains the definitions of formal languages, language classes (regular, context-free, etc.), and the Chomsky hierarchy.
- Designs finite state machines (DFA/NFA), pushdown automata, and Turing machines.
- Designs an automaton that uses proper language and proper grammar structure.
- Defines a non-regular language using a Push-Down Automata
Core Area Distribution
(48) Computing%50 (52) Engineering and Engineering Trades%50
Teaching Methods
ExpressionQuestion-AnswerExercise and PracticeProblem Solving
Assessment & Evaluation
Testing (Essay / Tests: True-Falls, multiple-choice, short answer, matching)
ECTS / Workload
| Activity | Quantity | Duration (h) | Total Workload |
|---|---|---|---|
| Course Duration (Including Exam Week) | 15 | 3 | 45 |
| Out of Class Study Period | 15 | 5 | 75 |
| Midterm | 1 | 2 | 2 |
| Quiz | 0 | 0 | 0 |
| Assignment | 0 | 0 | 0 |
| Practice | 0 | 0 | 0 |
| Final | 1 | 2 | 2 |
Course Schedule
| Week | Subject | Preparation |
|---|---|---|
| 1 | Concept of Formal Language, Concept of Automata Theory Introduction to Computation Theory (Sets, Functions, Relations, Graphs, Trees and Proof Methods) | Slides |
| 2 | Languages | Slides |
| 3 | Finite Automata | Slides |
| 4 | Finite Automata (continous) | Slides |
| 5 | Regular Sets and Regular Expressions | Slides |
| 6 | Grammar, Languages and Properties of the Regular Languages | Slides |
| 7 | Midterm | Midterm |
| 8 | Context-Free Languages and Grammars | Slayt |
| 9 | Simplifying Context-Free Grammars | Slides |
| 10 | Chomsky and Greibach Normal Forms | Slides |
| 11 | Pushdown Automata | Slides |
| 12 | Pushdown Automata (continues) | Slides |
| 13 | Turing Machines | Slides |
| 14 | Other Models of the Turing Machines | Slides |
| 15 | Final Exam | Final Exam |
| 16 | Final Exam | Final Exam |