Machines and Languages (Grundlagen der Theoretischen Informatik)
Dozent: Prof. Dr. Ute Schmid
(Kognitive Systeme)
Tutor: Francisco Macias, Ph.D.
(Grundlagen der Informatik)
Die Veranstaltung wird zweisprachig in Deutsch (Vorlesungen) und Englisch (Übungen) durchgeführt.
Schedule:
Lectures: Thursday 14:00 - 16:00 c.t., F380
Workshops:
Tuesday 16:00 - 18:00 c.t., Kä 1.112
Wednesday 16:00 - 18:00 c.t., Kä 0.154
Thursday 16:00 - 18:00 c.t., Kä 1.121 (Sprechstunde)
Fragestunde zur Probeklausur: Donnerstag
19.08. ab 14:00 Uhr in F380
Attendance to the workshop is not compulsory but highly advisable. You only need to attend
one of the three weekly sessions.
The First block of workshops starts during the second week of the semester; April 27th, 28th and
29th. The idea behind the workshops is to solve exercises related to the knowledge presented during
the lecture.
You can register to the workshops by writing your name in one the three lists that will be posted
(by April 21st) in the board outside the GdI department.
Overview
This course tries to answer the questions "what is a computation?" and "what is an algorithm?" and so to explore the capabilities and limitations of computers and programming languages as well as the implication of these for a practical computer scientist. We will introduce the concepts and methods that underlie the formal (mathematical) study of computing machines and analyse the nature of formal languages. At the end of this course the students should
- be able to distinguish finite automata, pushdown automata, and Turing machines
- be able to distinguish regular, context-free, context-sensitive and general phrase structure grammars
- understand the relations between language classes and machine classes
- understand the language parsing problem and be able to build simple LL(k), LR(k) parsers
- have developed elementary automata and Turing machine programming skills
- have gained insights into the fundamental nature of the halting problem and the classes of recursively computable and recursively enumerable sets (Church-Turing Thesis)
- be able to reason about the computational complexity of algorithms in terms of order-of-growth and the P and NP classification.
The course not only provides the basic elements in the theoretical foundation of Computer Science but also key logical and analytical skills in modelling and reasoning about discrete information systems that are useful in all areas of Computing and IT.
- Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, (2nd ed.) 2001. Deutsche Übersetzung: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, Pearson Studium, 2002, ISBN 3-8273-7020-5.
- Asteroth, A., Baier, Ch.: Theoretische Informatik, Pearson Studium, 2002, ISBN 3-8273-7033-7.
- Sudkamp, Th., A.: Languages and Machines, Addison-Wesley Longman, 1995.
- Martin, J., C.: Introduction to Languages and the Theory of Computation, McGraw Hill, (2nd ed.), 1997.
- Cohen, D. I. A.: Introduction to Computer Theory, Wiley, 2nd ed., 1997.
Classical Textbooks (may no longer be in print):
- Floyd, R.W. and Beigel, R.: The Language of Machines, W.H. Freeman, 1994.
- Revesz, G. E.: Introduction to Formal Languages, Dover, 1983.
- Brookshear, J. Glenn: Formal Languages, Automata, and Complexity, Benjamin Cummings, 1989.
- Interesting and/or entertaining background literature:
- Hodges, A. Alan Turing: The Enigma , Vintage, 1992.
- Arbib, M.A. Brains, Machines, and Mathematics, 2nd ed., Springer-Verlag, 1987.
- Penrose, R.: Shadows of the Mind: A Search for the Missing Science of Consciousness, Vintage, 1995.
- Hofstadter, D.: Gödel, Escher, Bach, Random House USA Inc, 1998.
- Smullyan, R.: Spottdrosseln und andere Metavögel. Fischer Taschenbuch, 1989. ISBN 3-596-28712-X
- Smullyan, R:: The Lady or the Tiger?. Oxford University Press, reissue, 2000. ISBN 0-19-280143-0
Course
Notes (Subject to changes!)
- Chap 0: Course Organisation
- Chap 1: Deterministic Finite Automata
- Chap 2.1: Regular Languages and Pumping Lemma
- Addenda to Chapters 0, 1 and 2.1: Automata, Monoids, Power Sets, Countable/Incountable Infinite
- Chap
2.2: Nondeterministic Finite Automata and Subset Construction
- Tutorial: Minimizing Deterministic Finite Automata
- Chap 3: Nondeterministic Finite Automata and Regular Grammars
- Chap 4: Regular Expressions and Kleene's Theorem
- Chap 5: Introduction to Pushdown Automata
- Chap 6: Context-free Grammars
- Chap 7: Pumping Lemma and the Limits of Context Free Languages
- Chap 8: Deterministic PDAs, LL(k) and LR(k) Parsing
- Chap 9: Introduction to Turing Machines
- Chap 10: Turing Machines as Language Acceptors
- Chap 11: Universal Turing Machine, Halting Problem, Computable Functions
- Chap 12: Time Complexity of Language Recognition Problems and the Classes P and NP
Exercise Sheets (Subject to changes!)
| Tuesday | Wednesday | Thursday | |
|---|---|---|---|
| Exercise Sheet 0 | 27.04.2010 |
28.04.2010 |
29.04.2010 |
| Exercise Sheet 1 | 04.05.2010 |
05.05.2010 |
Sprechstunde |
| Exercise Sheet 2 | 11.05.2010 |
12.05.2010 |
Bank Holiday |
| Exercise Sheet Extra 1 | 18.05.2010 |
19.05.2010 |
Sprechstunde |
| Exercise Sheet 3 | 25.05.2010 |
26.05.2010 |
Apologies |
| Exercise Sheet 4 | 01.06.2010 |
02.06.2010 |
Bank Holiday |
| Exercise Sheet Extra 2 | 08.06.2010 |
09.06.2010 |
Sprechstunde |
| Exercise Sheet 5 | 15.06.2010 |
16.06.2010 |
Sprechstunde |
| Exercise Sheet 6 | 22.06.2010 |
23.06.2010 |
Sprechstunde |
| Exercise Sheet 7 | 29.06.2010 |
30.06.2010 |
Sprechstunde |
| Exercise Sheet 8 | 06.07.2010 |
07.07.2010 |
Sprechstunde |
| Exercise Sheet 9 | 13.07.2010 |
14.07.2010 |
Auf Anfrage |
| Exercise Sheet 10 | 20.07.2009 |
21.07.2009 |
Übung um 14:00 Uhr anstelle der Vorlesung |
Tools
Have a look at the JFLAP tool for practical experiments with various types of automata, an introductory tutorial is available here . It also comes with a textbook: S. H. Rodger: JFLAP: An Interactive Formal Languages and Automata Package, Jones & Bartlett, 2006. Here are a couple of building blocks and composite Turing machines programmed in JFLAP. The following piece of advice may be useful:
- JFLAP uses two-sided tapes whereas in the lectures we have been working with one-sided tapes only. Also, in JFLAP the initial tape head is always positioned at the first symbol of the input string. Thus, in order to run the machines presented in the lectures it is necessary to program an additional head move to the left at the beginning of the program.
- In JFLAP (Version 6.0) it is necessary that each program in the block hierarchy starts with a dummy block "Start". If you leave out the Start block the exit transitions of the very first macro block inside a sub-program are not executed properly. (They are tested and executed before the macro block is entered rather than at the end when the block terminates. It seems that JFLAP expands initial states only down to level 2 of the hierarchy.)
- Note that JFLAP programs contain all their macro blocks in the same main file. This means that if you include a macro block and then want to change it you must either edit it in-place inside the main program or edit the original external macro program and include it into the main program again. Warning: Never use "save file" when editing a macro inside a program. It seems this can overwrite the main program.
- In multi-tape Turing machines always use the low-level explicit transitions to connect with macro blocks, never the higher-level block transitions. It seems that macro transitions are not fully implemented in Version 6.0. Please check later versions of JFLAP for fixes yourself.
- Note that variables (to store symbols read from the tape) cannot be negated. A negation !w means "not the symbol w" rather than "not the symbol read and stored into w". If you need to negate a stored variable (and cannot reformulate your problem in positive terms), you will have to expand the machine and program each symbol separately.
Pâté is a additional tool for the visual and interactive parsing (Bruteforce) and transforming (to CNF) of grammars. A online demo is available here.
-
An additional question time workshop session regarding the practice papers will be held in room F380 on thursday 19th august at 14:00.
- The course and exercise sheets may be both modified and extended as the course progresses. Any changes will be indicated on this page.
- Students are expected to complement their reading, over and above the course notes, with at least one of the recommended textbooks! Some of these textbooks (e.g., Martin or Sudkamp) include an huge amount of exercises which give excellent opportunity for practicing. The exercise sheets issued on this course only indicate the minimum requirements.
- The practice papers are suggestions for additional preparation only. Working them through cannot replace careful study of lecture notes and textbooks.