CM0081 Automata and Formal Languages (2024-1)

This page will be continuously updated during the course!


Course Information

Lecturer

Andrés Sicard Ramírez
Email address: asr(at)eafit(dot)edu(dot)co
Office hours

Official channel

  1. Lecturer

  2. Course Coordinator

  3. Head of Mathematical Engineering
    Francisco Iván Zuluaga-Díaz <fzuluag2(at)eafit(dot)edu(dot)co>

Lectures

Class 2123, 3:00 to 4:30 p.m
Wednesdays, room 35-203
Fridays, room 33-402

Textbook

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.).

Examination

Percentages

Activity %
Three exams 22%, 23% and 25%, respectively
Two programming labs 15% each

Dates and descriptions

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

Lecture Notes

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 ]
  • Algorithms on regular expressions [ .html ] [ .lhs ]
  • Java version of the isEmpty function (by Juan Francisco Cardona-McCormick)
§ 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.
  • {0n1n | n ≥ 1}[ .jff ]
  • Proper subtraction [ .jff ]
§ 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

Haskell and Agda Talks

Title Slides
Introduction to Haskell pdf ]
Regular Expressions in Haskell: An Introduction pdf ]
Introduction to Agda pdf ]