Captain's Log: Formal Language Theory, Spring 2009

1: January 16 (Friday)

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.

January 19 (Monday)

University Holiday (Martin Luther King)

2: January 21 (Wednesday)

Embark on Chapter 2, introducing DFAs (Section 2.2).
First Gradiance homework out.

3: January 23 (Friday)

Continue DFAs, constructing some automata and proving some general properties, through Exercises 2.2.4(a,b), 2.2.11, 2.2.2, 2.2.3, and 2.2.9.
Gradiance HW1 due at midnight.

4: January 26 (Monday)

Introduce NFAs (Section 2.3), motivated by the language of Exercise 2.2.5(b) which is also used to illustrate the subset construction.

5: January 28 (Wednesday)

Do the subset construction on an NFA for Exercise 2.2.5(c), ending up with essentially the same DFA we constructed last time.
In general, the size of a DFA may be exponential in the size of the NFA it was constructed from (the language in Exercise 2.2.5(b) is an example of that), though in other special cases it has essentially the same states (Exercise 2.3.6).
Construct the DFA of Exercise 2.2.6(a).
Construct the NFAs of Exercise 2.3.4(a,b).
Gradiance HW2 (on NFAs) due at midnight.

6: January 30 (Friday)

Finish chapter 2, by covering e-NFAs (Section 2.5), illustrated by Exercise 2.5.3(a,b).

7: February 2 (Monday)

Introduce Regular Expressions (Section 3.1), used by e.g. UNIX (cf. Section 3.3.1).
Do Exercise 3.1.1.
Gradiance HW3 (on e-NFAs) due at midnight.

8: February 4 (Wednesday)

Students do Exercise 3.1.2(b), Exercise 3.1.3(a,b,c), Exercise 3.1.4 (b,c).
List some algebraic laws for regular expressions (Section 3.4.1-3.4.5).
Assignment 1 due at 4pm.
Last day for 100 % refund.

9: February 6 (Friday)

We prove the correctness of a simple way of checking the validity of laws for regular expressions (Section 3.4.6-3.4.7), while pointing out that the method would fail if we add an intersection operator (even though intersection preserves the property of being regular). Show how to convert a regular expression into an e-NFA (Section 3.2.3).
Gradiance HW4 (on regular expressions) due tomorrow morning.

10: February 9 (Monday)

Show how to convert automata into regular expressions (Section 3.2.1-2), illustrated by Exercise 3.2.2.
Graded Assignment 1 back; briefly discuss model solutions (are on K-State Online).
Gradiance HW5 (on regular expressions versus finite automata) due tomorrow morning.

11: February 11 (Wednesday)

Briefly discuss how regular expressions are used for lexical analysis (Sect. 3.3.2).
Introduce the pumping lemma (Section 4.1), crucial for proving that a language is not regular as illustrated by Exercise 4.1.1(a) and Exercise 4.1.2(e).
Last day for 50 % refund.

12: February 13 (Friday)

Students do Exercise 4.1.2(c,d,f,g,h).
We also work our way through Exercise 4.1.4.
Start showing that regular languages are closed under certain operations (Sect. 4.2).
Gradiance HW6 (on whether languages are regular) due tomorrow morning.

13: February 16 (Monday)

Finish showing that regular languages are closed under certain operations (Sect. 4.2).
Do Exercise 3.2.6.
Gradiance HW7 (on operations on regular languages) due tomorrow morning.

14: February 18 (Wednesday)

Show how to check if two states in a DFA are equivalent, something which can be used to minimize a DFA; we illustrate the material (found in Section 4.4) by doing Exercise 4.4.2.
Tomorrow (Feb 19) is last day to drop without W being recorded.

15: February 20 (Friday)

Wrap up Chapter 4 by discussing decision procedures for regular languages (Sect. 4.3), and by doing Exercise 4.3.1.
(Revised) Assignment 2 (on paper) due at 4pm. (But can still be submitted until Monday at 4pm but 5p will be subtracted.)

16: February 23 (Monday)

We look at Exercise 4.2.8 (a language which one might not expect to be regular but which is), and our old friend Exercise 3.2.7.
Brief introduction to Context-Free Grammars (Section 5.1).
Gradiance HW8 (on DFA minimization) due tomorrow morning.

17: February 25 (Wednesday)

Show that the languages recognized by context-free grammars strictly (Exercise 5.1.1(a)) includes (Exercise 5.1.3) all regular languages. We elaborate on that point by showing how to translate a DFA into a CFG, cf. Exercise 5.1.4(b), and do one half of the correctness proof: by induction in string length, we show that all strings accepted by the DFA are also accepted by the CFG.
Gradiance HW9 (on strings recognized by CFGs) due tomorrow morning.

18: February 27 (Friday)

We do the other half of the correctness proof from last time: by induction on the length of the derivations, we show that all strings generated by the CFG are also accepted by the DFA.
Discuss when grammers are ambiguous, and what to do about that (Section 5.4).

19: March 2 (Monday)

Graded Assignment 2 back; discuss model solutions.
Do Exercises 5.1.8 and 5.4.1.
Assignment 3 (on paper) due at 4pm.
Gradiance HW10 (on various CFG issues) due tomorrow morning.

20: March 4 (Wednesday)

Exam I

21: March 6 (Friday)

Do Exercises 5.4.3 and 5.4.2. Also gave a grammar for non-palindromes.
Gradiance HW11 (on various CFG issues) due tomorrow morning.

22: March 9 (Monday)

Graded Exam 1 back; discuss selected questions.
Finish Exercise 5.1.1(c).
Embark on pushdown automata, introducing the configurations and the transitions between them (Section 6.1).

23: March 11 (Wednesday)

Discuss solutions to Assignment 3 (to be handed back soon).
Continue pushdown automata, with examples provided by Exercise 6.2.1(a,b,c); mention the two kinds of conditions for accepting a string (Section 6.2).

24: March 13 (Friday)

Illustrate how to convert a CFG into an equivalent PDA (Section 6.3).
Discuss deterministic pushdown automata (Section 6.4) which (by "final state") accept strictly more languages than finite-state automata but strictly less languages than general PDAs.
Assignment 4 (on paper) due at 4pm.

March 16-20

Spring break.

March 23-27

Class canceled (instructor out of town)
Monday, March 23, is last day to drop the course.
Gradiance HW12 (on PDAs) due late Friday, March 27.

25: March 30 (Monday)

Graded Assignment 4 back; discuss a couple of approaches.
Illustrate how to convert a PDA into an equivalent CFG, thus completing the argument that pushdown automata accept exactly the context-free languages (Section 6.3).
Simplify the CFG constructed above, thus motivating Section 7.1 on normalizing CFGs.
Gradiance HW13 (on PDAs and CFGs) due tomorrow morning.

26: April 1 (Wednesday)

Discuss how to simplify a CFG, ending up in Chomsky Normal Form (Section 7.1).

27: April 3 (Friday)

Students do Exercises 7.1.3,7.1.4,7.1.5.
State the pumping lemma for CFGs (Section 7.2), and give an example of its use (Example 7.19).

28: April 6 (Monday)

Prove the pumping lemma (Section 7.2) and give several applications, including Exercise 7.2.1(a).
Gradiance HW14 (on normal forms) due tomorrow morning.

29: April 8 (Wednesday)

Illustrate Ogden's lemma by applying it to Exercise 7.2.1(a).
Show that CFLs are closed under certain operations but not closed under other operations (Section 7.3).
Briefly discuss complexity and decidability issues (Section 7.4); whether a given string belongs to a given CFL can be answered effectively through the CYK algorithm.
Gradiance HW15 due tomorrow morning.

April 10 (Friday)

Class canceled (Good Friday)

30: April 13 (Monday)

Wrap up Chapter 7, in particular illustrate the CYK algorithm, and discuss the upcoming Assignment 5.
Do Exercises 7.3.4 and 7.3.5.
Gradiance HW16 due tomorrow morning.
Assignment 5 (on paper) due tomorrow at noon.

31: April 15 (Wednesday)

Exam II

April 17 (Friday)

Class canceled (All-University Open House)

32: April 20 (Monday)

Argue (using cardinality considerations) that many (most!) problems are undecidable, and give an example of an undecidable problem: the halting problem. (The presentation differs somewhat from Section 8.1 but has similar conclusions.)

33: April 22 (Wednesday)

Gradiance 17 due in the morning.
Reduce the undecidable halting problems to other problems, showing they are also undecidable (cf. Section 8.1).
Introduce the Turing machine (Sections 8.2 up to p.329).

34: April 24 (Friday)

Continue Section 8.2, giving examples of how to program a Turing machine: Exercise 8.2.1; Exercise 8.2.2(a).
Also motivate why a Turing machine can do everything a (human) computer can do, cf. Turing's original paper (pp 19-21).

35: April 27 (Monday)

Students do Exercises 8.2.2(b), 8.2.3(a).
Discuss techniques (Section 8.3) and extensions (Section 8.4) that make it easier to program a Turing machine.
Do Exercise 8.3.2 which implements a common subroutine; do Exercise 8.4.1(b) which illustrates how multiple tapes may convert quadratic runtime into linear runtime.
Graded Exam 2 back.

36: April 29 (Wednesday)

Student does Exercise 8.2.2(c).
Briefly discuss model solutions for Exam 2.
Mention nondeterministic Turing machines (Section 8.4.4), illustrated by Exercises 8.4.3(a) and 8.4.5(a,b).
Introduce machines that are even simpler than the Turing machine, yet having the same language-recognition power (Section 8.5, until 8.5.3).
Gradiance 18 (Turing-machines) due tonight.

37: May 1 (Friday)

Mention counter machines (Sections 8.5.3-8.5.4), doing Exercise 8.5.1(a,c).
Briefly relate Turing machines to standard computers (Section 8.6).

38: May 4 (Monday)

Embark on undecidability, introducing recursive languages and RE languages, covering Sections 9.1, 9.2, and 9.3.1.
The universal language is RE but not recursive; its complement is not even RE.

39: May 6 (Wednesday)

Introduce other problems that we can prove non-recursive by reduction from the universal language (Sect. 9.3), in particular state Rice's Theorem.

40: May 8 (Friday)

Introduce problems that are about "real things" (rather than about Turing machines) but are still undecidable (Sect. 9.5); a starting point is Post's Correspondence Problem (Sect. 9.4).
Graded Assignment 5 back.

May 11 (Monday)

Assignment 6 (on paper) due at 4pm.
Gradiance 19 (undecidability) due tonight.

May 13 (Wednesday)

Review session at 2-3pm in CIS library, going through Assignment 6 (handed back) and last year's final exam.

May 15 (Friday)

Final exam, 11:50am-1:40pm