MAL image

School of Computer Science
University of Nottingham
Jubilee Campus, Wollaton Road
Nottingham NG8 1BB, UK

T: +44(0) 115 9514251
F: +44(0) 115 9514254

HMU cover

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.

Outline of lectures

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.

DateTopicsLecture 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

Coursework and Feedback

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.

DateTestTopicsFeedback 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
Test 5 Lectures 17-20 28 Apr - 2 May

Contacting the teacher

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.