Theory of Computation (MAE745)

General

School	School of Science
Academic Unit	Department of Mathematics
Level of Studies	Undergraduate
Course Code	MAE745
Semester	7
Course Title	Automata Theory and Formal Languages
Independent Teaching Activities	Lectures (Weekly Teaching Hours: 3, Credits: 6)
Course Type	Special Background
Prerequisite Courses	-
Language of Instruction and Examinations	Greek
Is the Course Offered to Erasmus Students	Yes (in English)
Course Website (URL)	http://nlampp-lab.uoi.gr/lab/

Learning Outcomes

Learning outcomes

The goal of this course is the deeper understanding of Automata Theory and Languages. During the course a detailed examination of the following topics are done: Introductory concepts of Automata , Computability and Complexity as well as basic definitions, basic theorems and inductive proofs Finite State Machines and Languages, Finite Automata (Deterministic FA, Nondeterministic FA, FA with Epsilon-Transitions) and their applications, Regular Expressions and Languages, derivation trees. Removing Nondeterminism . Equivalence NFA and NFA with ε-moves. Minimization of DFA, Pumping Lemma FA and Grammars. Grammars of Chomsky Hierarchy. Regular Sets (RS). Properties of Regular Languages. RS and FA. Finding a correspondence Regular Expression of a FA. Abilities and disabilities of FA. Context-Free Grammars and Languages, Pushdown Automata (Deterministic PDA, Acceptance by Final State, Acceptance by Empty Stack) , Properties of Context-Free Languages. Correspondence PDA and Context-Free Languages. Introduction of Turing Machines. Standard TM, useful techniques for TM constructions. Modification of TM. TM as procedure. Unsolvability. The Church-Turing Thesis. The Universal TM. The Halting Problem for TM. Computational Complexity. NP-complete problems. After completing the course the student can handle: theoretical documentation of problems solving exercises tracking applications which related to Finite Automata, Pushdown Automata, and Turing Machines as well as to Unsolvability , to Computational Complexity and to NP-complete problems.

General Competences

Handle new problems Decision making Implementation- Consolidation

Syllabus

• Introductory concepts of Automata , Computability and Complexity as well as basic definitions, basic theorems and inductive proofs
• Finite State Machines and Languages, Finite Automata (Deterministic FA, Nondeterministic FA, FA with Epsilon-Transitions) and their applications, Regular Expressions and Languages, derivation trees. Removing Nondeterminism . Equivalence NFA and NFA with ε-moves. Minimization of DFA, Pumping Lemma
• FA and Grammars. Grammars of Chomsky Hierarchy. Regular Sets (RS). Properties of Regular Languages. RS and FA. Finding a correspondence Regular Expression of a FA. Abilities and disabilities of FA.
• Context-Free Grammars and Languages, Pushdown Automata (Deterministic PDA, Acceptance by Final State, Acceptance by Empty Stack) , Properties of Context-Free Languages. Correspondence PDA and Context-Free Languages.
• Introduction of Turing Machines. Standard TM, useful techniques for TM constructions. Modification of TM. TM as procedure.
• Unsolvability. The Church-Turing Thesis. The Universal TM. The Halting Problem for TM. Computational Complexity. NP-complete problems.

Teaching and Learning Methods - Evaluation

Delivery	Face to face
Use of Information and Communications Technology	Yes, use of Natural Language and Mathematical Problems Processing Laboratory
Teaching Methods	Activity Semester Workload Lectures 39 Self study 78 Exercises 33 Course total 150
Student Performance Evaluation	Final test

Attached Bibliography

• Βιβλίο [11776]: Στοιχεία θεωρίας υπολογισμού (Elements of Computation Theory), Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
• Βιβλίο [257]: ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ (Introduction in Computation Theory), SIPSER MICHAEL