**Class sessions:**** Thursdays and Fridays** 15:45 – 17:00, East Hall 8

**Topics:** Formal languages, discrete automata, first-order logic. This course gives an introduction to the most basic themes of theoretical computer science. Formal languages and discrete automata are the fundaments of programming languages and their parsing and compiling. First-order logic is the basis of artificial intelligence, program verification and advanced data base systems.

**Lecture notes***: self-contained, complete set of lecture notes. Latest version from September 30, differs from previous version only by adding parse tree for unambiguous grammar page 39*

**Further helpful documents:**

A collection of exercises and exams with solutions from 2003 (pdf)

A collection of exercises and exams with solutions from 2004 (pdf)

A collection of exercises and exams with solutions from 2005 (pdf)

The midterm and final exam questions with solutions, 2006 (pdf)

The final exam from 2010 with solutions (multiple choice format) (pdf)

**Additional reading:** a condensed intro to RDF, written by Jan Wilken Dörrie. To be enjoyed at the end of the lecture as this concerns a marriage between logic and grammars, of central importance for "semantic web" techologies.

**Course culture. **The online lecture notes are a fully self-contained, textbook-style, detailed text. Any exam questions are based solely on what is in the lecture notes. Thus, a student could perfectly pass this course by just home-studying the lecture notes, tuning his/her skills on the weekly homeworks, sit in the exams, and be done without ever seeing me. Ooops. I *do* want to see my students... Easy: I make classroom attendance mandatory. Ooops again - mandatory boredom? Solution: (i) mandatory classroom presence, (ii) mandatory pre-reading of the lecture note portion of the day, (iii) in class I will only briefly rehearse the pre-read lecture note material, making sure that everybody has a good grasp of it, and then (iv) I will spend most of the classroom time telling you stuff that is related to the lecture note material, but outside of it -- stuff you will not find in typical lecture notes: historical background, applications, connections of computer science to other sciences, tricky problems and open questions, math minitutorials, and more. This "extra" stuff will, I hope, make attendance worth its while, although it is not exam-relevant. You will, I hope very much, be amazed how deeply the technical material of this lecture is connected to realities outside CS.

**Grading and exams:** Grading and exams: The final course grade will be composed from homeworks (15%), presence sheets (10%), and quizzes/exams. There will be four miniquizzes (written in class, 20 minutes), the best three of which will each account to 15% of the final grade (worst will be dropped), and one final exam, counting 30%. All quizzes and the final exam are open book. Each quiz or exam yields a maximum of 100 points. The total semester points Pts_total are computed as the weighted semester point average (each quiz points are weighted by 0.15, the final by 0.30, etc.), and from Pts_total the final grade is computed by the standard Jacobs formula.

Miniquiz makeup rules: if a miniquiz is missed without excuse, it will be graded with 0 points. An oral makeup will be offered for medically excused miniquizzes according to the Jacobs rules (especially, the medical excuse must be announced to me on the day of the miniquiz). Non-medical excuses can be accepted and makeups be arranged on a case-by-case basis.

**References (optional! the online lecture notes suffice)**

- Hopcroft, John E., Motwani, Rajeev, and Ullman, Jeffrey:
*Introduction to Automata Theory*, 2nd (Addison-Wesley).*The standard textbook for most parts of this lecture, except for the logic part*. IRC: QA267 .H56 2001 -
Schoening, Uwe: Logic for Computer Scientists (Progress in Computer Science and Applied Logic, Vol 8), (Birkhauser). The book contains what its title suggests. IRC: QA9 .S363 1989

**Schedule (this will be filled in synchrony with reality as we go along)**

Sep 1 |
Introduction |

Sep 2 | Alphabets, words, languages, and cardinalities. |

Sep 8 | DFAs. Reading for Sep 8: Lecture Notes Section 3 up to (excluding) Definition 3.4 Exercise sheet 1 |

Sep 9 | NFAs. Power set construction. Application: text search algorithm. Epsilon-NFAs. Reading for today: LN Section 3.1 complete. |

Sep 15 | Regular expressions and equivalence to DFAs. Reading: LN Section 3.2. Exercise sheet 2 |

Sep 16 | Regexps with language variables. Algebraic laws for regexps. Pumping lemma. Reading: LN Sections 3.3, 3.4 Solutions to exercise sheet 1 |

Sep 22 | Closure properties of regular languages. Language homomorphisms. Quiz prep. Reading: LN Section 3.5 Solutions to exercise sheet 2 Exercise sheet 3 |

Sep 23 | Miniquiz 1. Myhill-Nerode theorem. No reading. |

Sep 29 | Myhill-Nerode theorem and minimization of DFAs. Reading: LN Section 3.6 Solutions to exercise sheet 3 Exercise sheet 4 |

Sep 30 | Context-free languages: basic definitions and examples. Ambiguity. Connection to regular languages. Reading: Sections 4.1, 4.2 |

Oct 6 | The powers of XML. Reading: Section 4.4 Solutions to sheet 4 Exercise sheet 5 |

Oct 7 | Pushdown automata, part 1. Reading: Section 4.5 up to (including) Def. 4.13 |

Oct 13 | Pushdown automata, part 2. Reading: Section 4.5 to its end. Solutions for exercises 5 Exercise sheet 6 |

Oct 14 | Miniquiz 2 Chomsky normal form. No reading. |

Oct 20 | The CYK algorithm. Some (non)decidability results. Wrap-up formal languages. Reading: Section 4.6 to end, skip Section 4.7, read Section 4.8. Solutions to sheet 6 Exercise sheet 7 |

Oct 21 | Introducing first-order logic: motivation. Signatures. Reading: LN Section 6, Section 7 up to (including) Example 7.2 |

Oct 27 | Syntax of FOL. Reading: LN Section 7.1 |

Oct 28 | Training session: formalizing parts of the real world in FOL. No reading. Solutions to sheet 7 Exercise sheet 8 |

Nov 3 | Semantics of FOL: S-structures, S-interpretations. Reading: LN Section 7.2 up to Def. 7.7. Solutions to sheet 8 Exercise sheet 9 |

Nov 4 | Miniquiz 3 S-structures, completed. No reading |

Nov 10 | Training session: S-structures. No reading. |

Nov 11 | The model relationship. Reading: LN Section 7, all of it. |

Nov 17 | The sequent calculus. Reading: LN Section 8 up to the summary table of derivation rules Solutions to sheet 9 Exercise sheet 10 |

Nov 18 | Derivations. Reading: LN Section 8, complete preparation sheet for miniquiz 4 |

Nov 24 | The completeness theorem. Reading: LN Section 9 up to (excluding) Theorem 9.5 |

Nov 25 | Miniquiz 4 The unique role of FOL in mathematics and AI. No reading. |

Dec 1 | (optional) A brief outline of Herbrand theory, the basis for modern logic inference engines (part 1). No reading |

Dec 2 | (optional) A brief outline of Herbrand theory, the basis for modern logic inference engines (part 2). No reading |

Dec 20 | Final exam 12:30 - 14:30 Conference Hall (IRC) |