Machines and their Languages (G52MAL)

Machines and their Languages studies the abstract concept of computing machines and their use to generate and recognise 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 learnt 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.

Textbooks

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

As main reference we are using the book by Thomas A. Sudkamp, Languages and Machines (I will refer to it by SUD 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).

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.

Date	Topics	Lecture Notes
1. 29 Jan 2013	Introduction to the Module Alphabets, Words and Languages	ANN Chapter 1 SUD Chapter 2: 2.1, 2.2
2. 31 Jan 2013	Deterministic Finite Automata	ANN Chapter 2: 2.1 SUD Chapter 5: 5.1, 5.2, 5.3
3. 5 Feb 2013	Nondeterministic Finite Automata	ANN 2.2 SUD 5.4, 5.5, 5.6
4. 7 Feb 2013	Equivalence of DFA and NFA	...
5. 12 Feb 2013	Regular Expressions Characterization by NFA	ANN Chapter 3 SUD 2.3, 6.1-6.4
6. 14 Feb 2013	Minimization of DFA	ANN Chapter 4 SUD 5.7
7. 19 Feb 2013	Example of Minimization of DFA Pumping Lemma	ANN Chapter 5 SUD Chapter 6.6
8. 21 Feb 2013	An Automata Videogame Context-Free Grammars (CFG)	Jahooma's Logic Box CFG Animator ANN Chapter 6; SUD Chapter 3: 3.1, 3.2
9. 28 Feb 2013	Context-Free Grammars Introduction to Pushdown Automata (PDA)	ANN Chapter 7: 7.1, 7.2, 7.3 SUD Chapter 7: 7.1
10. 5 Mar 2013	Pushdown Automata	ANN 7.4, 7.5 SUD 7.3
11. 7 Mar 2013	From CFG to PDA	...
12. 12 Mar 2013	Optional topics: not in the exam Chomsky Normal Form, Pumping Lemma for CFL	ANN: missing SUD 4.2-4.5, 7.4
13. 14 Mar 2013	Recursive Descent Parsing 1 Guest Lecturer Henrik Nilsson	Slides Printable formats: 4 per page, 9 per page
14. 19 Mar 2013	Recursive Descent Parsing 2 Guest Lecturer Henrik Nilsson	Slides Printable formats: 4 per page, 9 per page
15. 21 Mar 2013	Recursive Descent Parsing 3 Guest Lecturer Henrik Nilsson	Slides Printable formats: 4 per page, 9 per page
16. 23 Apr 2013	Turing Machines	ANN 9.1 SUD 8.1
17. 25 Apr 2013	TM as language acceptors Constructing a TM	...
18. 30 Apr 2013	Recursively Enumerable Languages Recursive Languages	ANN Chapter 9 SUD 8.2
19. 2 May 2013	Turing Computability The Halting Problem	...
End of lectures

Coursework and Tutorials

Every two weeks you will find an assignment on this page. You have to solve the given problems and hand you solutions in by the following Thursday at 16:00 at the school office (stamp the assignment and put it in the letter box).

The following week the teaching assistants will demonstrate the solutions during the tutorials. You will be divided into four groups, each having a tutorial on a different day and time. If you're unable to attend the tutorial you've been assigned to, contact one of the teaching assistants, Laurence Day or Bas van Gijzel and ask to change your group.

Write on the cover letter of the assignment what group you belong to.

Your coursework mark will be the average of the best four assignments out of five; it counts for 25% of your final mark.

You will find your group and the day, time and room of your tutorial here: G52MAL tutorials 2013. The first tutorial takes place in the week 4-8 February: It will give you a chance to ask any question about the first few lectures.

Date	Assignment	To be handed in	Tutorial Week
Thu 7 Feb	Assignment 1	Thu 14 Feb	18-23 Feb
Thu 14 Feb	Assignment 2	Thu 21 Feb	25 Feb - 1 Mar
Thu 21 Feb	Assignment 3	Thu 28 Feb	4-8 Mar
Thu 28 Feb	No Assignment This Week	...	...
Thu 7 March	Assignment 4	Thu 14 March	18-22 Mar
Thu 14 March	Assignment 5	Thu 28 March	22-24 Apr
...	Assignment 6	Cancelled	...

Be sure to read carefully the regulations about submission of coursework and plagiarism in the student handbook. In addition to those regulations, assignments must be submitted at the latest by the end of the week of their official deadline and standard penalties apply.

Contacting the teacher

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.