First Cycle - Faculty of Engineering - Computer Engineering (English)
Y : Year of Study S : Semester
Course Unit Code Course Unit Title Type of Course Y S ECTS
CSE3064 Formal Languages and Automata Theory Compulsory 3 6 6
Objectives of the Course
To give students a broad overview of the theoretical foundations of Computer Science . To prepare students for study of topcics that depends on an understanding of formal languages and automata. To combine many different engineering areas and natural sciences, medicine, mathematics, linguistics, and other disciplines of computer science. To determine what can and cannot be computed by answering the question "what makes some problems computationally hard and others easy? To realize that statement: if a language cannot be informally defined, it is difficult to use a computer to process it in a consistent manner. To be informed that formal languages underlie all of computer science. To be able to unify all features of computers inspecting them abstractly. To understand the formal properties of the language (programming and natural) concept. To understand major results of automata and formal language theory and their relation with computer applications.
Learning Outcomes
1 Define Turing machines
2 use and define recursive functions to solve problem
3 Use and define automata, regular expressions and context-free grammars to solve problems
4 Differentiate between various finite automata, regular expressions and languages, context-free grammars and languages
5 Learn the theory and principle of automata theory
Mode of Delivery
Formal Education
Course Contents
Classification of automata and formal languages. Finite state machines, regular languages and their limitations. Tape automata. Push-down automata and context-free languages. Normal-form grammars. Context-sensitive languages. Turing machines, halting problem and unsolvability. Recursive functions.
Weekly Detailed Course Contents
Week Theoretical Practice Laboratory
1 Mathematical Preliminaries , Alphabets and Languages, Finite Representation of Languages
2 Three Basic Concepts: Languages, Grammars, Automata
3 Regular Expressions and Regular Languages
4 Finite State Machines with Output
5 Deterministic Finite Acceptors
6 Nondeterministic Finite Acceptors
7 Equivalance of Deterministic and Nondeterministic Acceptors
8 Equivalance of Deterministic and Nondeterministic Acceptors - Repeat
9 Official Holiday
10 Midterm
11 Kleene's Theorem, Minimal Finite Acceptor
12 Regular Languages and Nonregular Languages
13 Regular Languages and Regular Grammar
14 Context-Free Languages and Pushdown Automata
15 Top-Down Parsing &Bottom-Up Parsing
16 The Definition of Turing Machine, Combining Turing Machines
17 Final
Recommended or Required Reading
Introduction to Automata Theory, Languages, and Computation
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Planned Learning Activities and Teaching Methods
Lecture notes, programming assignments, quizzes.
Assessment
AssessmentQuantityWeight
Term (or Year) Learning Activities60
End Of Term (or Year) Learning Activities40
Total100
Term (or Year) Learning ActivitiesQuantityWeight
Midterm Exam150
Quiz Exam125
Homework Exam125
Total100
End Of Term (or Year) Learning ActivitiesQuantityWeight
Final Exam1100
Total100
Language of Instruction
English
Work Placement(s)
None
Workload Calculation
Activities Number Time (hours) Total Work Load (hours)
Theoretical 3 14 42
Midterm Preparation 1 10 10
Final Preparation 1 20 20
Quiz Preparation 1 5 5
Home Work 1 15 15
Project 1 15 15
Research Presentation 1 5 5
Field Study 1 4 4
Other 1 34 34
Total 11 122 150
Contribution of Learning Outcomes to Programme Outcomes
PO 1PO 2PO 3PO 4PO 5PO 6PO 7PO 8PO 9PO 10PO 11PO 12PO 13PO 14PO 15PO 16
LO 10000000000000000
LO 20000000000000000
LO 30000000000000000
LO 40000000000000000
LO 50000000000000000

^