Captain's Log: Formal Language Theory, Spring 2011

1: January 19 (Wednesday)
Go through syllabus.
Introduction and motivation.
Cover Section 1.5, giving the basic concepts of automata theory.
Before next time, you should read Chapter 1.
2: January 21 (Friday)
We introduce DFAs (Section 2.2) and do Exercises 2.2.4(a,b,c) and 2.2.5(b).
First Gradiance homework out.
3: January 24 (Monday)
Gradiance 1 due Tuesday night.
4: January 26 (Wednesday)
Introduce NFAs (Section 2.3), motivated by the language of Exercise 2.2.5(b) which is also used to illustrate the subset construction.
We then constructed an NFA for the language in Exercise 2.2.5(c), wrote down the claims needed for a correctness proof, and again did the (lazy) subset construction.
5: January 28 (Friday)
Continue NFAs, doing Exercises 2.3.4(a,b,c) where for (c) we also embarked on a correctness proof.
January 31 (Monday)
University closed due to inclement weather.
Gradiance 2 due tonight.
February 2 (Wednesday)
Class canceled due to road/sidewalk conditions.
6: February 4 (Friday)
Finish chapter 2, by covering e-NFAs (Section 2.5), illustrated by Exercise 2.5.3(a,b) and particularly useful for text recognition (Exercise 2.4.1(a,b)).
7: February 7 (Monday)
We introduce Regular Expressions (Section 3.1), as used by UNIX (Section 3.3.1), and do Exercise 3.1.1(a,b).
Gradiance 3 due tonight.
Paper assignment 1 due tomorrow Tuesday at 4pm.
8: February 9 (Wednesday)
We continue regular expressions, listing some algebraic laws (Section 3.4.1-3.4.5), and doing Exercises 3.1.1(c) and 3.1.2(a,b).
9: February 11 (Friday)
Gradiance 4 due tonight.
10: February 14 (Monday)
Gradiance 5 (on regular expressions versus automata) due tomorrow night.
11: February 16 (Wednesday)
12: February 18 (Friday)
We continue discussing the pumping lemma:
13: February 21 (Monday)
Show that regular languages are closed under certain operations (Sect. 4.2).
Gradiance 6 (on which languages are regular) due at midnight.
14: February 23 (Wednesday)
We do various exercises: 4.1.2(e) by Scott, 4.1.2(f) by Hequing, 4.2.2 & 3 by Rohit, 4.2.6(c) by Nic, 4.2.7 by Marcel.
15: February 25 (Friday)
With Exercise 4.4.2 as illustrating example, we show how to
  1. check if two states in a DFA are equivalent (Sect. 4.4.1-2)
  2. use the equivalence classes to construct the minimal DFA (Sect. 4.4.3).
Gradiance 7 (on operations on languages) due at midnight.
16: February 28 (Monday)
We wrap up Chapter 4: Assignment 2 (implementing DFA to RE conversion) due tomorrow at 4pm.
17: March 2 (Wednesday)
Introduce Context-Free Grammars (CFGs) (Sections 5.1 & 5.2). Gradiance 8 (on DFA minimization) due tonight.
18: March 4 (Friday)
Gradiance 9 (on basics of CFGs) due tonight.
19: March 7 (Monday)
We present two CFGs for balanced parentheses, cf. Exercise 5.3.2, and prove them equivalent.
20: March 9 (Wednesday)
Exam I.
21: March 11 (Friday)
We discuss when grammers are ambiguous, and what to do about that (Section 5.4):
22: March 14 (Monday)
Do Exercises 5.4.1-3, on a grammar that abstracts "if then (else)" constructs: Graded Exam I & Assignment 3 back; discuss selected questions.
23: March 16 (Wednesday)
Wrap up Chapter 5: Gradiance 11 (more advanced questions on CFGs) due tomorrow night.
24: March 18 (Friday)
Embark on pushdown automata, with an example provided by Exercise 6.2.1(a): Paper Assignment 4 due at 4pm.
March 21-25
Spring break.
25: March 28 (Monday)
Recall PDAs by doing Show how to Graded Assignment 4 back.
26: March 30 (Wednesday)
Prove that pushdown automata accept exactly the context-free languages (Section 6.3), by showing Simplify the CFG constructed above, thus motivating Section 7.1 on normalizing CFGs.
27: April 1 (Friday)
Mention a hierarchy: deterministic PDAs accept (by "final state") Discuss how to simplify a CFG (Section 7.1), by Gradiance 12 (on PDAs) due tonight.
28: April 4 (Monday)
29: April 6 (Wednesday)
Focus on the pumping lemma (Section 7.2): Gradiance 13 (on CFG normal forms) due tonight.
30: April 8 (Friday)
Gradiance 14 (misc CFL) due Sunday night.
31: April 11 (Monday)
Exam II
32: April 13 (Wednesday)
Discuss complexity and decidability issues (Section 7.4);
April 15 (Friday)
Class canceled (All-University Open House)
33: April 18 (Monday)
34: April 20 (Wednesday)
Focus on how to program a Turing machine, by doing Exercises 8.2.1 and 8.2.2(a,b).
Gradiance 15 (advanced CFL) due tonight.
April 22 (Friday)
Class canceled (Good Friday)
35: April 25 (Monday)
Continue Turing Machines:
36: April 27 (Wednesday)
Wrap up Turing machines: Gradiance 16 (Turing machines) due tonight.
37: April 29 (Friday)
Embark on undecidability, covering most of Sections 9.1 & 9.2:
38: May 2 (Monday)
Cover Section 9.3:
39: May 4 (Wednesday)
40: May 6 (Friday)
May 9 (Monday)
Paper Assignment 6 due at 4pm.
May 11 (Wednesday)
Review session from noon to 1pm in N236.
Gradiance 17 (undecidability) due tonight.
May 13 (Friday)
Final exam, 11:50am-1:40pm


Torben Amtoft