INF210 - Modelling of Computing

Contents on this web page

• Course outline and curriculum
• Teachers
• Schedule
• Semester plan
• Exercises
• Exam

Course outline and curriculum

The course revolves around formal languages and how this connects with computing. It covers mathematical models of computing like finite automata, pushdown automata and Turing Machines. It also covers grammar formalisms which centers around context-free with limitations (regular) and generalisations. The connection between automata, grammars, formal languages and limits of computational models (P, NP) are covered.

Reading Material

The curriculum consists of all lectures, notes, handouts, exercises, and related course material. There are many books on this topic and the student is free to choose among these.

Different books have slightly different notation, definitions and theorems, and may do proofs in different ways. Often the ordering of material also deviates, even between editions of the same book. Some relevant books:

• Harry R. Lewis and Christos H. Papadimitriou: Elements of the theory of Computation. Prentice-Hall, 1981. ISBN 0-13-273426-5.
• Thomas A. Sudkamp: Languages and Machines - An Introduction to the Theory of Computer Science. Addison-Wesley, 1988. ISBN 0-201-15768-3.

Teachers

Lecturer and course responsible: Magne Haveraaen
Teaching assistant: Jonathan Cubides

The participants are adviced to organise study groups for discussing the topics of the course and assist each other in solving the exercises.

Schedule for lectures and seminar groups

After some initial confusion we finally ended up with the following teaching times.

• Monday 1415 - 1600 in seminar room 405O2 ("aquarium") Høyteknologisenteret, exercise class, starting week 5
• Thursdays 0815 - 1000 in seminar room 405O2 ("aquarium") Høyteknologisenteret, lectures
• Fridays 1215 - 1400 in seminar room 405O2 ("aquarium") Høyteknologisenteret, lectures

Semester plan

3. Introduction, formal languages, the Chomsky hierarchy
4. Regular languages (RL), regular expressions (Re), DFA (deterministic finite automata), NFA (clairvoyant finite automata), ε-NFA, *-NFA and their languages
5. Theorems on the equivalence of all finite automata (they define the same class of formal languages) and the closure properties of these language (they define the regular languages)
6. Re-NFA, pumping theorem for regular languages, regular grammars and equivalence with finite automata, definition of homomorphisms on strings (monoid homomorphisms) and theorems about homomorphisms and languages
7. Context-free grammars (CFG) and languages (CFL), closure properties, normal forms
8. More normal forms for CFG, including Chomsky and Greibach normal forms
9. —
10. PDA (clairvoyant 1-stack automata), ext-PDA, theorem CFL⊆L(PDA)
11. Theorem L(PDA)⊆CFL
12. Pumping theorem for CFL, closure properties of CFL
13. —
14. —
15. 2-stack automata and Turing machines, decidable (recursive – R) and acceptable (recursive enumerable – RE) languages
16. Easter break
17. Equivalence between deterministic and clairvoyant Turing machines, P versus NP
18. Universal Turing machine as an interpreter of Turing machines versus running a Turing machine, closure properties for RL CFL R RE (also mentioning conjunctive and boolean grammars), general grammars (GG) and equivalence with RE.
19. Last details of proof for L(GG)=RE, summary of language classes and their relationsships, general grammars as computational devices (rewrite systems)
20. —
21. —
22. —
23. —
24. Exam

Exercises

Exam