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)

• We show that a DFA solving Exercise 2.2.5(b) really needs a lot of states.
• We give the recipe for proving that a given DFA accepts a given language, and illustrate it on the DFA from Exercise 2.2.4(a).

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)

• We show how to convert a regular expression into an e-NFA (Section 3.2.3), illustrated by Exercise 3.2.4 (c) with Exercise 3.2.7 showing pitfalls.
• We show how to convert automata into regular expressions by state elimination (Section 3.2.2), illustrated by Exercise 3.2.2(e).
• We show how to convert automata into regular expressions by incrementally building all possible paths (Section 3.2.1), illustrated by a simple example.

Gradiance 4 due tonight.

10: February 14 (Monday)

• We present 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).
• Hand back graded Assignment 1, and discuss some issues (model solutions are on K-State Online).
• We briefly discuss how regular expressions are used for lexical analysis (Sect. 3.3.2).

Gradiance 5 (on regular expressions versus automata) due tomorrow night.

11: February 16 (Wednesday)

• Wrap up Chapter 3, by showing how to prove that a given regular expression, (10+0)*(1+e), denotes a given language, the strings with no consecutive 1s.
• Introduce the pumping lemma (Section 4.1), crucial for proving that a language is not regular, as illustrated by Exercise 4.1.1(a).

12: February 18 (Friday)

We continue discussing the pumping lemma:

• we apply it (Example 4.2);
• we prove it;
• we show situations where it cannot be applied (Exercise 4.1.4(a-c)).

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:

• Exercise 4.2.6(a,b) by Ashish.
• Show that the DFA resulting from minimization is indeed the smallest possible (Sect. 4.4.4) but the minimization algorithm doesn't work for NFAs.
• Briefly discuss the complexity of various conversions/decision procedures (Sect. 4.3).

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).

• Do Exercise 5.1.1(a), giving a CFG for a non-regular language.
• We do one part of the correctness proof: that all strings generated by the CFG do indeed belong to the language.

Gradiance 8 (on DFA minimization) due tonight.

18: March 4 (Friday)

• We finish Exercise 5.1.1(a), proving that all strings in the language are generated by the CFG.
• We show (Exercise 5.1.3) that the languages recognized by CFGs include all regular languages.
  (The inclusion is strict, cf. Exercise 5.1.1(a).)

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.

• Paper Assignment 3 due at 4pm.
• Gradiance 10 (advanced questions on CFGs) due tomorrow night.

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):

• we can often convert into an unambiguous grammar, as for arithmetic expressions
• but some grammars are inherently ambiguous

22: March 14 (Monday)

Do Exercises 5.4.1-3, on a grammar that abstracts "if then (else)" constructs:

• we show how to make it unambigious, and
• we also give an exact characterization of the strings it generates.

Graded Exam I & Assignment 3 back; discuss selected questions.

23: March 16 (Wednesday)

Wrap up Chapter 5:

• Elaborate on Exercise 5.4.2 and do Exercise 5.1.8, thus preparing for Assignment 4.
• Do Exercise 5.4.7
• Briefly sketch Exercise 5.1.1(b,c)

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):

• introduce the configurations, and the transitions between them (Section 6.1);
• mention the two kinds of conditions for accepting a string (Sections 6.2.1 & 6.2.2).

Paper Assignment 4 due at 4pm.

March 21-25

Spring break.

25: March 28 (Monday)

Recall PDAs by doing

• Exercise 6.2.1(c) which allows a deterministic automaton (as defined in Section 6.4.1)
• Example 6.1 where non-determinism is needed

Show how to

• convert a PDA that accepts by empty stack into one that accepts by final state; this will preserve the property of being deterministic
• convert a PDA that accepts by final state into one that accepts by empty stack; this might lose the property of being deterministic (since deterministic PDAs that accept by empty stack can only recognize a limited class of languages)

Graded Assignment 4 back.

26: March 30 (Wednesday)

Prove that pushdown automata accept exactly the context-free languages (Section 6.3), by showing

• how to convert a CFG into an equivalent PDA, and
• how to convert a PDA into an equivalent CFG.

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")

• strictly more languages than finite-state automata, but
• strictly less languages than general PDAs.

Discuss how to simplify a CFG (Section 7.1), by

• removing useless symbols
• removing epsilon and unit productions.

Gradiance 12 (on PDAs) due tonight.

28: April 4 (Monday)

• Introduce Chomsky Normal Form (Section 7.1.5), and do Exercise 7.1.3.
• State the pumping lemma for CFGs (Section 7.2), and illustrate its use (Example 7.19).

29: April 6 (Wednesday)

Focus on the pumping lemma (Section 7.2):

• we give further applications such as Example 7.20
• we introduce the stronger version known as Ogden's lemma (Exercise 7.2.3)
• we use Exercise 7.2.5 (a) to show that Ogden's lemma can be easier to use than the original pumping lemma

Gradiance 13 (on CFG normal forms) due tonight.

30: April 8 (Friday)

• Show that CFLs are closed under certain operations but not closed under other operations (Section 7.3).
• We sketch how to prove the pumping lemma(s).
• One more application of the pumping lemma (Example 7.21) with Ogden's lemma being a bit easier to use (Exercise 7.2.4)
• Paper Assignment 5 due at 4pm.

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);

• whether a given string belongs to a given CFL can be answered effectively through the CYK algorithm, as illustrated by Exercise 7.4.3(b) (along the way we also did Exercise 7.4.5).

April 15 (Friday)

Class canceled (All-University Open House)

33: April 18 (Monday)

• Graded Exam II & Assignment 5 back; discuss selected questions.
• Introduce the Turing machine (Section 8.2).

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:

• Introduce multitape machines (Section 8.4.1) which for Exercise 8.2.2 (we worked out part c) allows to improve quadratic runtime into linear runtime (cf. Exercise 8.4.1).
• Show that a multitape Turing machine can be simulated, in quadratic time, by a one-tape machine (Sections 8.4.2-3).
• The above simulation illustrates several techniques (Section 8.3) to facilitate programming.
• Introduce nondeterministic Turing machines (Section 8.4.4), which can be simulated by deterministic Turing machines, but probably not in polynomial time...
• Mention that Turing machines and "standard computers" can simulate each other (Section 8.6).

36: April 27 (Wednesday)

Wrap up Turing machines:

• Introduce machines that are even simpler than the Turing machine, yet have the same language-recognition power (Section 8.5, illustrated by Exercise 8.5.1).
• Briefly mention Turing's argument that his machine can do everything a (human) computer can do, cf. Turing's original paper (pp 19-21).

Gradiance 16 (Turing machines) due tonight.

37: April 29 (Friday)

Embark on undecidability, covering most of Sections 9.1 & 9.2:

• introduce recursive languages (Section 9.2.1, cf. the RE languages defined in Section 8.2.5).
• introduce the universal language which is accepted by the universal Turing Machine and thus is RE.
• introduce the "diagonal language" and show that it is not RE.

38: May 2 (Monday)

Cover Section 9.3:

• Show that the universal language is not recursive since its complement is not even RE.
• Doing so, we introduce the technique of reduction which can be used to show that other problems are non-recursive or even non-RE.
• State Rice's Theorem: it is undecidable whether the language accepted by a given Turing machine has a certain property (unless that property is either always true or always false).

39: May 4 (Wednesday)

• Illuminate the concepts recently covered, by doing
  • Exercise 9.3.1 (where Rice's Theorem directly applies), and
  • Exercises 9.3.6(a) & 9.3.4(a).
• Introduce Post's Correspondence Problem (Section 9.4) which is about "real things" (rather than about Turing machines) but is still undecidable.

40: May 6 (Friday)

• Show, using the fact that PCP is undecidable, that many problems about Context-Free Grammars are undecidable (Section 9.5).
• Argue (using cardinality considerations) that many (most!) problems are undecidable, cf. the box on p.318 in the textbook.

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