Machines and their Languages studies the abstract concept of computing machines and their use to generate and recognize formal languages.
A series of abstract machines, classes of formal languages, and their relation is investigated, along with important practical applications of this theory, in particular language recognition (lexical and syntactic analysis). Ultimately the investigations touch on the question of what can and cannot be computed. Topics covered include: finite state machines, regular expressions, context-free grammars, push-down automata, parsing, and Turing machines.
At the end of the module you will have learned the central concepts of formal language and automata theory, such as finite automata and context-free grammars, and their applications. This will give you an introduction to computability theory.
You will understand the equivalence between machine types and language types, the nature of formal languages and their specification by grammars and other notations, the practical and theoretical relevance of machines that process strings from an alphabet of symbols as models of computation, and the fundamental limits on what is computable by any machine.
In the course of the module we will implement different abstract computing machines in Haskell. So it is important that you review that programming language and make sure that you are confident with it.
The main textbook for the module is Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman (I will refer to it by HMU from now on).
The module is based on a series of lecture notes by Thorsten Altenkirch and Henrik Nilsson, Machines and their Languages: Lecture notes (I will refer to them by ANN from now on). There is also a good revision guide by Michael B. Gale and Laurence E. Day (I will refer to it by GLR).
Two other excellent reference books for the same material are: Languages and Machines by Thomas A. Sudkamp and Introduction to Languages and the Theory of Computation by John C. Martin.
In this section you will find, after each lecture, a list of topics that were taught and references to the lecture notes and books. We're constantly trying to improve these notes, so I encourage you to tell me if you find mistakes or things that are not clearly explained.
Date | Topics | Lecture Notes |
---|---|---|
1. 30 Jan 2014 | Introduction to the Module Alphabets, Words and Languages |
HMU Chapter 1: 1.5 (review 1.1-1.4) ANN Chapter 1 |
2. 31 Jan 2014 | Deterministic Finite Automata | HMU Capter 2: (2.1,) 2.2 ANN Chapter 2: 2.1 |
3. 6 Feb 2014 | Nondeterministic Finite Automata | HMU 2.3 ANN 2.2 |
4. 7 Feb 2014 | Equivalence of DFA and NFA | ... |
5. 13 Feb 2014 | Regular Expressions Characterization by NFA |
HMU Chapter 3: 3.1, (3.2.3) ANN Chapter 3 |
6. 14 Feb 2014 | Minimization of DFA | HMU Chapter 4: 4.4 ANN Chapter 4 |
7. 20 Feb 2014 | Haskell Exercise (DFA and NFA) The Pumping Lemma |
HMU 4.1 ANN Chapter 5 |
8. 21 Feb 2014 | An Automata Videogame | Jahooma's Logic Box |
9. 27 Feb 2014 | Context-Free Grammars (CFG) | HMU Chapter 5: 5.1, 5.2 ANN Chapter 6 CFG Animator |
10. 28 Feb 2014 | DFA and NFA in Haskell Guest Lecturer Ambrus Kaposi |
Solution of Haskell Exercise |
11. 6 Mar 2014 | Pushdown Automata | HMU Chapter 6: 6.1, 5.2 ANN Chapter 7 |
12. 7 Mar 2014 | From CFG to PDA | HMU 6.3 |
13. 13 Mar 2014 | Parsing and LL(1) Grammars | ANN Chapter 8 |
14. 14 Mar 2014 | Recursive Descent Parsing Haskell Exercise |
Notes by Henrik Nilsson Part 1 (4 per page,9 per page) Part 2 (4 per page, 9 per page Part 3 (4 per page, 9 per page) |
15. 20 Mar 2014 | Turing Machines | HMU Chapter 8: 8.1, 8.2 ANN Chapter 9: 9.1 |
16. 21 Mar 2014 | TM as language acceptors Constructing a TM |
ANN 9.2 |
17. 27 Mar 2014 | Recursively Enumerable and Recursive Languages Turing Computability and the Halting Problem |
ANN 9.3 |
18. 28 Mar 2014 | LL(1) Grammars in Haskell Guest Lecturer Bas van Gijzel | Solution of Haskell Exercise |
19. 3 Apr 2014 | Exam topics and structure SET survey | ... |
The coursework consists in five short tests on Moodle. Every two weeks you will find a quiz on the Moodle page. The quiz consists of 10 short questions; you have 30 minutes to answer them all. Access to the quiz will be open for the whole specified day. You can choose at what time you want to do it, but once you start you have half hour to complete it. You must solve it by yourself with no help from others. Be sure to read carefully the regulations about plagiarism in the student handbook. Each quiz will cover the material of the lectures up to the quiz's date.
Your coursework mark will be the average sum of the scores of all the tests; it counts for 25% of your final mark.
On the Moodle page there is a forum. You can use it to ask for feedback on any topic from the lectures and on the tests. On the week after each test, two teaching assistants will specifically be answering questions about the quiz on the forum.
Date | Test | Topics | Feedback Week |
---|---|---|---|
Wed 12 Feb | Test 1 | Lectures 1-4 | 17-21 Feb |
Wed 26 Feb | Test 2 | Lectures 5-8 | 3-7 Mar |
Wed 12 Mar | Test 3 | Lectures 9-12 | 17-21 Mar |
Wed 26 Mar | Test 4 | Lectures 13-16 | 31 Mar - 4 Apr |
Wed 16 Apr Cancelled |
Test 5 | Lectures 17-20 | 28 Apr - 2 May |
I will have office hours on Tuesday from 13:00 to 15:00 and Friday from 15:00 to 16:00. My office is A07 in the Computer Science Building. You can come and ask any question about the material explained in the lectures.
Please don't hesitate to ask me any question you may have about the module. You can contact me by e-mail: put G52MAL in the subject line, so I know immediately that it is about this module.