Lecturers: Martin Fränzle (MF) and Michael R. Hansen (MRH).
The course covers regular and context-free languages, and an introduction to functional programming.
In the first part of the course we will study regular languages, and different ways of representing them. A part of the theory is constructive, and this part will be accompanied with program constructions given both in lectures and as exercises.
In the second part of the course we will study context-free languages, and different ways of representing them, e.g. context-free grammars and Pushdown automata. We shall relate context-free grammars to e.g. DTDs describing XML documents and algebraic datatypes of functional languages. Furthermore, we shall introduce techniques for parsing an input, thereby building a tree-representation, on the basis of certain kinds of grammars. These techniques originate from compiler construction, but they are also useful in many other application dealing with structured data.
Abbreviations:
| Week | Date | Topic | Read | Exercises | Programs | Lecturer |
|---|---|---|---|---|---|---|
| 36 | 30. Aug. |
Introduction to Languages and parsing; Introduction to SML. |
Browse through HMU: 1.1 to 1.3; read HMU 1.5. HR: Ch. 1. | Introduction to using SML in the G-databar. | MRH | |
| 36 | 2. Sept. | SML: Basic type, Tuples, Records, Recursion | HR Ch. 2, 3 and 4 | Exercises in the databar. | MRH | |
| 37 | 6. Sept. | Introduction to formal proofs | HMU 1.4 | Exercises in formal proof. | MF | |
| 37 | 9. Sept. |
Deterministic Finite Automata (DFA) Nondeterministic Finite Automata (NFA) |
HMU 2.1 - 2.3.4 |
Ex. HMU 2.2.4. Ex. HMU 2.2.5(b,c,d). Ex. HMU 2.2.7 (Hint: You may use induction on strings, as introduced in the lecture of Sept. 6, rather than induction on their length.); show that if the initial state of a DFA A satisfies the conditions of Ex. 2.2.7, then either L(A) is empty or L(A) contains all strings over the alphabet of A. |
MF | |
| 38 | 13. Sept. | SML: Lists Programs for DFAs |
HR Ch. 5 | Exercises | Solutions to HR ex 2.6 and 2.7 | MRH |
| 38 | 16. Sept. | NFA, Product and Complement, Equivalence of NFA and DFA | HMU 2.3, HMU p. 133(Theorem 4.5) to p.136 |
Repeat Ex. HMU 2.2.5(b), this time constructing an
NFA. Ex. HMU 2.3.1, 2.3.2 Ex. HMU 2.3.4(c) Ex. HMU 4.2.14 (a,d) |
MF | |
| 39 | 20. Sept. |
Part I:
Boolean operations on automata and emptiness test; Part II: Datatypes in SML Simple Automata Library |
HR: Ch. 7 | 7.1, 7.2, 7.3. + Exercises | SimpleDFA.sml SimpleSet.sml |
MF, MRH |
| 39 | 23. Sept. | Epsilon-NFAs, Regular expressions | HMU 2.5, 3.1, 3.2.1, 3.2.3 | Ex. HMU 2.5.1, 2.5.2, 2.5.3; Ex. HMU 3.1.1, 3.1.2, 3.1.4, 3.1.5. |
MF | |
| 40 | 27. Sept. |
Pumping Lemma; Closure properties of regular languages |
HMU 4.1, 4.2 | Ex. HMU 3.2.4; Ex. HMU 4.1.1(a,f), 4.1.2(f), Ex. HMU 4.2.1(a,...,e), 4.2.2. |
MF | |
| 40 | 30. Sept. |
Decision Properties of Regular languages; Automaton minimization |
HMU 4.3, 4.4 |
Ex. HMU 4.3.1, 4.3.3, 4.3.5 Ex. HMU 4.4.1, 4.4.3 Databar assistance from 11.00-12.00 concerning exercises from Sept. 20. |
MF | |
| 41 | 4. Oct. |
SML: Finite Trees Regular expressions |
HR Ch. 8 | Exercises | regularExSkeleton.sml | MRH |
| 41 | 7. Oct. | Summary of Regular Language Theory | HMU Ch. 5.1, 5.2 | Ex. HMU 2.2.9, 2.3.3, 3.2.1 (a-d), 4.1.1 (b), 4.1.2 (c) | MF | |
| 43 | 18. Oct. | AVLtrees Rehearsal of SML Solution to the map colouring problem A paper from Frontiers in Education 1999 |
8.3, 8.6 + old exercises not yet solved | avlTrees.sml avlLog.sml | MRH | |
| 43 | 21. Oct. | Higher-order functions | HR Ch. 9 | 9.1, 9.2, 9.3 | MRH | |
| 44 | 25. Oct. | Context-Free Grammars and Languages | HMU Ch. 5.1, 5.2 | Ex. HMU 5.1.1 (a), 5.1.2, 5.1.4 Ex. HMU 5.2.1 |
MRH | |
| 44 | 28. Oct. |
Ambiguity in CFLs, Introduction to Pushdown Automata |
HMU Ch. 5.3.1, 5.4, HMU Ch. 6.1, 6.2 |
Ex. HMU 5.3.1, 5.3.2, Ex. HMU 5.4.1, 5.4.3, 5.4.7 |
MRH | |
| 45 | 1. Nov. | Shift-Reduce parsing; Scanning using mosmllex; Parsing using mosmlyacc | HMU 5.3.2; Moscow ML Owner's Manual pp. 29-34. |
Exercises Solutions: Absyn.sml, Exprpar.grm, Exprlex.lex |
Programs | MRH |
| 45 | 4. Nov. | Scanning using mosmllex; Parsing using mosmlyacc; Exampe: XML; | HMU 5.3.3, 5.3.4 | Remaining exercises from last week; Simple exercise on scanning and parsing XML |
MRH | |
| 46 | 8. Nov. |
NO LECTURE. Work with Mandatory Assignment 2. Consultance MRHs office (322/011) 13-17 Databar assistance 15-17 |
MRH | |||
| 46 | 11. Nov. |
NO LECTURE. Work with Mandatory Assignment 2. Consultance MRHs office (322/011) 8.15-12.00 Databar assistance 10-12 |
MRH | |||
| 47 | 15. Nov. |
Deterministic pushdown automata; Reductions and normal forms for CFGs |
HMU Ch. 6.4; HMU Ch. 7.1 |
HMU Ex. 6.3.1 HMU Ex. 6.4.1, 6.4.2 HMU Ex. 7.1.1, 7.1.6 |
Thomas Bolander | |
| 47 | 18. Nov. | Pumping lemma for CFLs; Closure properties for CFLs |
HMU Chapter 7.2, 7.3 | HMU Ex. 7.2.1, (a, b, c); HMU Ex. 7.3.1 (a), 7.3.2 |
MRH | |
| 48 | 22. Nov. | Decision
properties for CFLs Old examination question 49409 Automata, Languages and Computability Solutions |
HMU Chapter 7.4 | HMU Ex. 7.4.1 (a,b), 7.4.3, 7.4.4 | MRH | |
| 48 | 25. Nov. |
NO LECTURE. Work with Mandatory Assignment 3. Consultance MRHs office (322/011) 8.15-12.00 Assistance is exercise classs 10-12 |
MRH | |||
| 49 | 29. Nov. | Old examination questions | From 2002 From 2003 |
MRH | ||
| 49 | 2. Dec. | Course Evaluation: Starts at 11.00 | MRH |