This page will be continuously updated during the course!
Andrés Sicard
Ramírez
Email address:
asr(at)eafit(dot)edu(dot)co
Office
hours
Lecturer
Course Coordinator
Head of Mathematical Engineering
Francisco Iván
Zuluaga-Díaz
<fzuluag2(at)eafit(dot)edu(dot)co>
Class 2123, 3:00 to 4:30 p.m
Wednesdays, room 35-203
Fridays, room 33-402
John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman (2007). Introduction To Automata Theory, Languages, and Computation, 3rd edition. Pearson Education, Inc. Book site (errata, solution to the starred exercises, etc.).
| Activity | % |
|---|---|
| Three exams | 22%, 23% and 25%, respectively |
| Two programming labs | 15% each |
| Activity | Week | Date/Dealine | Description/Textbook material |
|---|---|---|---|
| Exam 1 | 6th | Wednesday, February 28 |
§ 1.5 The Central Concepts of Automata Theory
§ 2.2 Deterministic Finite Automata § 2.3 Non-Deterministic Finite Automata § 2.4 An Application: Text Search § 2.5 Finite Automata With Epsilon-Transitions § 3.1 Regular Expressions |
| Programming Lab 1 | 10th | Friday, April 5, 11:59 p.m. | Testing Regular Expressions Matching |
| Exam 2 | 11th | Wednesday, April 10 |
§ 3.2 Finite Automata and Regular Expressions
§ 3.3 Applications of Regular Expressions § 3.4 Algebraic Laws for Regular Expressions § 4.1 Proving Languages Not to Be Regular § 4.2 Closure Properties of Regular Languages |
| Exam 3 | 17th | Wednesday, May 22 |
§ 8.1 Problems That Computers Cannot Solve
§ 8.2 The Turing Machine § 9.1 A Language That Is Not Recursively Enumerable § 9.2 An Undecidable Problem That Is Recursively Enumerable § 9.3 Undecidable Problems About Turing Machines § 9.4.1 Definition of Post's Correspondence Problem |
| Programming Lab 2 | 18th | Monday, May 27 (11:59 p.m.) | Normalisation in the Lambda Calculus |
| Subject | Slides | Other |
|---|---|---|
| Course Introduction | [ pdf ] | N/A |
| § 1.4 Formal Proofs | [ pdf ] | N/A |
| § 1.5 The Central Concepts of Automata Theory | [ pdf ] | N/A |
| § 2.2 Deterministic Finite Automata | [ pdf ] | Functional representation of a DFA [ .hs ] |
| § 2.3 Non-Deterministic Finite Automata | [ pdf ] | N/A |
| § 2.5 Finite Automata with Epsilon-Transitions | [ pdf ] | N/A |
| § 3.1 Regular Expressions | [ pdf ] | |
| § 3.2 Finite Automata and Regular Expressions | [ pdf ] | N/A |
| § 3.4 Algebraic Laws for Regular Expressions | [ pdf ] | N/A |
| § 4.1 Proving Languages Not to Be Regular | [ pdf ] | N/A |
| § 4.2 Closure Properties of Regular Languages | [ pdf ] | N/A |
| § 8.1 Problems That Computers Cannot Solve | [ pdf ] | N/A |
| § 8.2 Turing Machines | [ pdf ] | Turing machines simulation using JFLAP (version 7.1, July 27, 2018). Tested on Ubuntu Focal (20.04.6 LTS) and OpenJDK 17. |
| § 9.1 A Language That Is Not Recursively Enumerable | [ pdf ] | N/A |
| § 9.2 An Undecidable Problem That Is Recursively Enumerable | [ pdf ] | N/A |
| § 9.3 Undecidable Problems About Turing Machines | [ pdf ] | N/A |
| § 9.4.1 Undecidable Problems | [ pdf ] | N/A |
| The Church-Turing-Kleene Thesis | [ pdf ] | N/A |
| Hypercomputation | [ pdf ] | N/A |
| Title | Slides |
|---|---|
| Introduction to Haskell | [ pdf ] |
| Regular Expressions in Haskell: An Introduction | [ pdf ] |
| Introduction to Agda | [ pdf ] |