Theory of Computation (MAE745)
Από Wiki Τμήματος Μαθηματικών
Αναθεώρηση ως προς 18:26, 29 Ιουνίου 2022 από τον Mathwikiadmin (συζήτηση | συνεισφορές) (→Learning Outcomes)
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:
After completing the course the student can handle:
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 |
|
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 |
| ||||||||||
| Student Performance Evaluation |
Final test |
Attached Bibliography
- Βιβλίο [11776]: Στοιχεία θεωρίας υπολογισμού (Elements of Computation Theory), Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
- Βιβλίο [257]: ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ (Introduction in Computation Theory), SIPSER MICHAEL