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 eNFAs (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.13.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 eNFA
(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.63.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 KState 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(ac)).

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

check if two states in a DFA are equivalent (Sect. 4.4.12)

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 ContextFree Grammars (CFGs)
(Sections 5.1 & 5.2).

Do Exercise 5.1.1(a), giving a CFG
for a nonregular 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.13, 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 2125

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 nondeterminism 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 contextfree 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 finitestate 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 (AllUniversity 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 onetape machine
(Sections 8.4.23).

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 languagerecognition 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 1921).
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 nonrecursive or even nonRE.

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 ContextFree 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:50am1:40pm
Torben Amtoft