EPOKA UNIVERSITY
FACULTY OF ARCHITECTURE AND ENGINEERING
DEPARTMENT OF COMPUTER ENGINEERING
COURSE SYLLABUS
2025-2026 ACADEMIC YEAR
COURSE INFORMATIONCourse Title: THEORY OF COMPUTATION |
| Code | Course Type | Regular Semester | Theory | Practice | Lab | Credits | ECTS |
|---|---|---|---|---|---|---|---|
| CEN 350 | C | 6 | 2 | 2 | 0 | 3 | 6 |
| Academic staff member responsible for the design of the course syllabus (name, surname, academic title/scientific degree, email address and signature) | Dr. Halit Vural hvural@epoka.edu.al |
| Main Course Lecturer (name, surname, academic title/scientific degree, email address and signature) and Office Hours: | Dr. Halit Vural hvural@epoka.edu.al , Will be announced |
| Second Course Lecturer(s) (name, surname, academic title/scientific degree, email address and signature) and Office Hours: | NA |
| Language: | English |
| Compulsory/Elective: | Elective |
| Study program: (the study for which this course is offered) | Bachelor in Computer Engineering (3 years) |
| Classroom and Meeting Time: | Tue 9:00~11:30 |
| Teaching Assistant(s) and Office Hours: | NA |
| Code of Ethics: |
Code of Ethics of EPOKA University Regulation of EPOKA University "On Student Discipline" |
| Attendance Requirement: | Yes |
| Course Description: | This course introduces the theory of computation through a set of abstract machines that serve as models for computation - finite automata, pushdown automata, and Turing machines - and examines the relationship between these automata and formal languages. Additional topics beyond the automata classes themselves include deterministic and non-deterministic machines, regular expressions, context free grammars, undecidability, and the P = NP question. |
| Course Objectives: | This course introduces the mathematical foundations of computation. Students study formal languages, finite automata, context-free grammars, pushdown automata, Turing machines, and basic computational complexity. Beyond theory, the course emphasizes how these abstract models power real systems including: * Search engines and pattern matching * Compilers and programming languages * Network protocol verification * Input validation and cybersecurity * Artificial intelligence parsing systems The goal is not memorization of definitions, but understanding how different computational models capture different levels of machine capability. |
|
BASIC CONCEPTS OF THE COURSE
|
| 1 | Formal Languages and Alphabets - Alphabet (Σ) Strings and string operations Languages as sets of strings Language operations (union, concatenation, Kleene star) |
| 2 | Finite Automata - Deterministic Finite Automata (DFA) Nondeterministic Finite Automata (NFA) Extended transition functions Language recognition Equivalence between DFA and NFA |
| 3 | Regular Languages - Regular expressions Regular grammars Closure properties Pumping Lemma for Regular Languages |
| 4 | Context-Free Grammars (CFG) - Production rules Derivations and parse trees Ambiguity Simplification techniques Normal forms (Chomsky Normal Form, Greibach Normal Form) |
| 5 | Pushdown Automata (PDA) - Stack-based computation Instantaneous descriptions Equivalence between PDA and CFG |
| 6 | Properties of Context-Free Languages - Closure properties Pumping Lemma for Context-Free Languages |
| 7 | Turing Machines - Formal definition of Turing Machine Configurations and computation sequences Language acceptance Variants and equivalence |
| 8 | Decidability and Computability - Decidable and undecidable problems Recursive and recursively enumerable languages The Halting Problem Reductions |
| 9 | Language Hierarchy - Regular Languages Context-Free Languages Recursive Languages Recursively Enumerable Languages |
| 10 | Computational Complexity - Time complexity Polynomial vs exponential growth Complexity classes (P, NP) |
|
COURSE OUTLINE
|
| Week | Topics |
| 1 | Introduction to the theory of computation |
| 2 | Mathematical Preliminaries and Notation |
| 3 | Deterministic Finite Automata (DFA) |
| 4 | Nondeterministic Finite Automata (NFA) |
| 5 | NFA to DFA Conversion |
| 6 | Regular Expressions |
| 7 | Properties of Regular Languages |
| 8 | Context-Free Grammars (CFG) |
| 9 | Midterm |
| 10 | Pushdown Automata (PDA) |
| 11 | Equivalence of CFG and PDA |
| 12 | Turing Machines |
| 13 | Decidability and Undecidability |
| 14 | Compilers and Parsing |
| Prerequisite(s): | An introduction to programming, is Discrete Mathematics: propositional logic, proof methods including induction, graphs, basic number theory, sets, functions, and relations. |
| Textbook(s): | An introduction to formal languages and automata; Peter Linz, Susan H. Rodger; (7th Edition) Jones & Bartlett Learning, [2023]; ISBN 9781284231601 |
| Additional Literature: | Theory of Computation: Making Connections; Jim Hefferon; (2nd Edition), Free available at: hefferon.net ----------------- Introduction to Theory of Computation, Anil Maheshwari, Michiel Smid, 2024 |
| Laboratory Work: | Yes |
| Computer Usage: | Yes |
| Others: | No |
|
COURSE LEARNING OUTCOMES
|
| 1 | Analyze computational problems and determine the appropriate formal model (finite automaton, pushdown automaton, or Turing machine) for solving them. |
| 2 | Construct and formally specify deterministic and nondeterministic finite automata, regular expressions, context-free grammars, pushdown automata, and Turing machines. |
| 3 | Apply closure properties and pumping lemmas to prove whether a language is regular or context-free. |
| 4 | Explain the limits of algorithmic computation, including undecidability and the Halting Problem, using formal reasoning. |
| 5 | Differentiate between tractable and intractable problems and explain the significance of complexity classes such as P and NP. |
| 6 | Relate formal language and automata theory to practical applications such as compilers, pattern matching, input validation, and syntax analysis. |
| 7 | Communicate formal computational concepts clearly through written proofs, diagrams, and structured explanations. |
| 8 | Use computational tools (e.g., automata simulators) to model, test, and analyze formal systems. |
|
COURSE CONTRIBUTION TO... PROGRAM COMPETENCIES
(Blank : no contribution, 1: least contribution ... 5: highest contribution) |
| No | Program Competencies | Cont. |
| Bachelor in Computer Engineering (3 years) Program | ||
| 1 | Engineering graduates with sufficient theoretical and practical background for a successful profession and with application skills of fundamental scientific knowledge in the engineering practice. | 4 |
| 2 | Engineering graduates with skills and professional background in describing, formulating, modeling and analyzing the engineering problem, with a consideration for appropriate analytical solutions in all necessary situations | 5 |
| 3 | Engineering graduates with the necessary technical, academic and practical knowledge and application confidence in the design and assessment of machines or mechanical systems or industrial processes with considerations of productivity, feasibility and environmental and social aspects. | 2 |
| 4 | Engineering graduates with the practice of selecting and using appropriate technical and engineering tools in engineering problems, and ability of effective usage of information science technologies. | 3 |
| 5 | Ability of designing and conducting experiments, conduction data acquisition and analysis and making conclusions. | 2 |
| 6 | Ability of identifying the potential resources for information or knowledge regarding a given engineering issue. | 3 |
| 7 | The abilities and performance to participate multi-disciplinary groups together with the effective oral and official communication skills and personal confidence. | 2 |
| 8 | Ability for effective oral and official communication skills in foreign language. | 3 |
| 9 | Engineering graduates with motivation to life-long learning and having known significance of continuous education beyond undergraduate studies for science and technology. | 4 |
| 10 | Engineering graduates with well-structured responsibilities in profession and ethics. | 1 |
| 11 | Engineering graduates who are aware of the importance of safety and healthiness in the project management, workshop environment as well as related legal issues. | 1 |
| 12 | Consciousness for the results and effects of engineering solutions on the society and universe, awareness for the developmental considerations with contemporary problems of humanity. | 3 |
|
COURSE EVALUATION METHOD
|
| Method | Quantity | Percentage |
| Homework |
2
|
5
|
| Midterm Exam(s) |
1
|
30
|
| Project |
1
|
10
|
| Laboratory |
5
|
2
|
| Term Paper |
1
|
|
| Final Exam |
1
|
40
|
| Total Percent: | 100% |
|
ECTS (ALLOCATED BASED ON STUDENT WORKLOAD)
|
| Activities | Quantity | Duration(Hours) | Total Workload(Hours) |
| Course Duration (Including the exam week: 16x Total course hours) | 16 | 4 | 64 |
| Hours for off-the-classroom study (Pre-study, practice) | 16 | 4 | 64 |
| Mid-terms | 1 | 10 | 10 |
| Assignments | 2 | 1 | 2 |
| Final examination | 1 | 10 | 10 |
| Other | 0 | ||
|
Total Work Load:
|
150 | ||
|
Total Work Load/25(h):
|
6 | ||
|
ECTS Credit of the Course:
|
6 | ||
|
CONCLUDING REMARKS BY THE COURSE LECTURER
|
|
Regular attendance is essential for successful completion of this course. Students are expected to attend the group in which they are officially registered. Group changes are not permitted unless approved and processed by the course coordinator. Maintaining proper group alignment ensures fairness, effective classroom management, and equal learning opportunities for all students. Active participation during class hours is highly valued. Students are expected to collaborate with their peers, engage in discussions, and contribute to in-class activities. Note-taking is considered an important part of the learning process. The lecture slides alone are not sufficient learning material and should not be treated as complete study notes. Students are expected to prepare before class by reviewing relevant materials and to reinforce their learning after class. This includes reviewing personal lecture notes, reading additional resources, consulting textbooks, and study. |