Formal Languages and Logic, Fall 2018 (CO21320352)
Jacobs University Bremen, Fall 2018, Herbert Jaeger
Class sessions: Tuesdays 9:4511:00 (Lecture Hall Res. 1), Thursdays 11:1512:30 (West Hall 8)
Office hours:No regular office hours. If I'm in my office and you want to see me, knock and enter and I will have time. If you want to make sure that I am in, drop me an email for fixing an appointment.
Topics: Formal languages, discrete automata, firstorder 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. Firstorder logic is the basis of artificial intelligence, program verification and advanced data base systems.
Lecture notes: selfcontained, complete set of lecture notes. Last update Oct 17 Updated Oct 17, 2018 (typos, font conversion errors, updated URLs, nothing crucial)
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 selfcontained, textbookstyle, detailed text. All exam questions are based solely on what is in the lecture notes. Thus, a student could perfectly pass this course by just homestudying 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 prereading of the lecture note portion of the day, (iii) in class I will only briefly rehearse the preread 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 examrelevant. You will, I hope very much, be amazed how deeply the technical material of this lecture is connected to realities outside (and underneath) CS.
Grading and exams: Grading and exams: The final course grade will be composed from homeworks (15%), presence sheets (10%), and quizzes (45%) and a final exam (30%). There will be three miniquizzes (written in class, 30 minutes), the best two of which will be counted (worst will be dropped). All quizzes and the final exam are open book. Each quiz or exam yields a maximum of 100 points.
Miniquiz makeup rules: if a miniquiz is missed without excuse, it will be graded with 0 points. A makeup will be offered for medically excused miniquizzes according to the Jacobs rules (specifically, the medical excuse must be announced to me before the miniquiz). Nonmedical excuses can be accepted on a casebycase basis.
References (optional! the online lecture notes suffice)
 Hopcroft, John E., Motwani, Rajeev, and Ullman, Jeffrey: Introduction to Automata Theory, 2nd (AddisonWesley). 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 4  Introduction 
Sep 6  Basic notation. The concept of a formal language. Two kinds of infinities, one of them kind, the other a brute. (= Lecture notes Section 2) Exercise sheet 1 
Sep 11  Deterministic Finite Automata (DFAs) and Nondeterministic Finite Automata (NFAs). Reading: LN Section 3 up to (including) Example 3.3. 
Sep 13  Equivalence of DFAs and NFAs. Reading: LN Section 3 up to (excluding) Def. 3.7. Exercise sheet 2 Solutions to exercise sheet 1 
Sep 18  no class (illness) 
Sep 20  epsilonNFAs, Moore and Mealy machines. Reading: LN Section 3.1 complete Solutions to exercise sheet 2 
Sep 25  Regular expressions and their equivalence with DFAs. Reading: LN Section 3.2 (we skip the material in 3.3) Slides: a zoo of finitestate system models (and for the ambitious ones: here is the full dynamical systems course slideset) 
Sep 27  Pumping Lemma and closure properties of regular languages. Reading: LN Sections 3.4, 3.5. Exercise sheet 3 (extended version, now covering 2 weeks) 
Oct 2  First miniquiz (in CNLH!) MyhillNerode theorem. No reading, fyi: material covered will be the theorem statement and its proof, found in the beginning of LN Section 3.6. 
Oct 4  Minimization of DFAs. Decision properties of regular languages (lecturer of the day: Xu He) Reading: LN Section 3.6 to end Exercise sheet 4 Solutions to exercise sheet 3 
Oct 9  Grammars: basic definitions. Reading: LN Sections 4.1 
Oct 11  Ambiguity. Grammars for regular languages. Reading: LN Sections 4.2, 4.3 Exercise sheet 5 Solutions to exercise sheet 4 
Oct 16  Pushdown automata. Reading: no reading expected. Class will be held by Xu He. 
Oct 18  The magic of XML. Reading: LN Sections 4.4 Solutions to exercise sheet 5 Exercise sheet 6 
Oct 25  Finishing PDAs. Chomsky Normal Form. Reading: LN Sections 4.5, 4.6 Exercise sheet 7 
Oct 30  Closure properties of CFLs and the CYK algorithm. Reading: LN Section 4.8 Solutions to exercise sheet 6 
Nov 1  Grammars: final remarks. Other kinds of Grammars. Chomsky hierarchy. Reading: LN Section 5 Solutions to exercise sheet 7 Exercise sheet 8 (a very lightweight one) 
Nov 6  Second miniquiz (venue: CNLH) Introduction to firstorder logic. No reading. 
Nov 8  Syntax of FOL. Reading: LN Section 7.1 Solutions to exercise sheet 8 Exercise sheet 9 
Nov 13  Formalizing pieces of the world in FOL  training session. No reading 
Nov 15  Semantics of FOL 1: Sstructures. Reading: LN Section 7.2 up to (excluding) Def. 7.6 Solutions to exercise sheet 9 Exercise sheet 10 
Nov 20  Semantics of FOL 2: Sinterpretations. Model relation and logical entailment Reading: LN Section 7.2 complete. 
Nov 22  Another training session: examples of Sstructures, model relation, and entailment. No reading. Solutions to exercise sheet 10 Exercise sheet 11 
Nov 27  Entailment  concluding remarks. The sequent calculus: intro. Reading: LN Section 8 (up to and including the list of rules). 
Nov 29  Derived rules. Derivations in the sequent calculus. Reading: LN Section 8, complete. Exercise sheet 12, with solutions, for selfstudy (do not return) 
Dec 4  Third miniquiz (venue: CNLH). Followed by time for online course evaluation. A zoo of logics  informal overview. No reading. 
Dec 6  Completeness of FOL. Concluding remarks. Reading: LN Section 9 up to (including) proof sketch of completeness theorem. 
Dec 15  Final exam: 9:0011:00, SCC Hall 3 