Captain's Log: Formal Language Theory, Spring 2014

1: January 22 (Wednesday)


Go through syllabus.

Introduction and motivation.

Cover Section 1.5, giving the basic concepts of automata theory.

We outline the content of the course,
divided in 3 parts with increasingly powerful (but increasingly complex)
language formalisms.
Before next time, you should read Chapter 1.

2: January 24 (Friday)

We introduce DFAs (Section 2.2), illustrated by

the language of strings with an even number of 0s, and

the language of strings with an odd number of 0s and
an odd number of 1s.
Gradiance 1 due at midnight.

3: January 27 (Monday)

We see more examples of DFA construction:

students do
Exercises 2.2.4(b) and 2.2.4(c) and 2.2.5(c)

together we do Exercise 2.2.5(b)
(with "third" rather than "tenth")
and also show how to solve it using a
nondeterministic automaton (cf. Section 2.3).
We briefly discussed Gradiance 2, due tomorrow at midnight.

4: January 29 (Wednesday)


We give the recipe for proving
that a given DFA accepts a given language,
and illustrate it
(cf. notes uploaded on KState Online)
on the DFA from Exercise 2.2.4(a).

Continue NFAs (Section 2.3),
with focus on the (lazy) subset construction
as illustrated for
an NFA for Exercise 2.2.5(b)
(with "second" rather than "tenth").

5: January 31 (Friday)

We see more examples of NFA construction:

students do
Exercises 2.3.4(b) and 2.3.4(c);

together we
again look at Exercise 2.2.5(c):
we first construct an NFA and list the meaning
of each state (as would be needed for a correctness proof);
next we by the (lazy) subset construction convert it into a DFA
which can be compressed by merging "equivalent" states.
Gradiance 3 due at midnight.

6: February 3 (Monday)


We use Exercise 2.3.4(a) to illustrate (cf. notes uploaded on
KState Online) how
to prove the correctness of an NFA.

Introduce eNFAs (Section 2.5), illustrated by Exercise 2.5.3(a)
for which we also do the conversion into a DFA.

February 5 (Wednesday)

University closed due to snow.
Gradiance 4 due at midnight.

7: February 7 (Friday)

We wrap up eNFAs:

students do Exercises 2.5.3(b) and 2.4.1(b)

we sketch how to prove correctness
(cf. notes uploaded on KState Online).
We introduce Regular Expressions (Section 3.1),
and look at Exercise 3.1.4(b).

8: February 10 (Monday)

We continue regular expressions,
as used by UNIX (Section 3.3.1):

we list some algebraic laws
(Section 3.4.13.4.5).

we do Exercises
3.1.1(a & b)
and 3.1.4 (a & c).
Last day for 100% refund.
Assignment 1 due at 4pm.
Gradiance 5 due Tuesday night.

9: February 12 (Wednesday)


Students do Exercises 3.1.1(c) and 3.1.2(b).

We show how to convert
a regular expression into an eNFA
(Section 3.2.3),
illustrated by Exercise 3.2.4(c).

We show how to convert automata into regular expressions
by state elimination
(Section 3.2.2),
illustrated by Exercise 3.2.2(e).

10: February 14 (Friday)


Student does Exercise 3.2.7, showing pitfalls
in the translation from RE to eNFA
(premature optimization is the root of all evil!)

We illustrate another method (Section 3.2.1)
for conversion from FA to RE:
incrementally build all possible paths,
as illustrated by a simple example.

We do Exercise 3.2.6(a&b).
Gradiance 6 due tonight.

11: February 17 (Monday)


Discuss and hand back graded Assignment 1.

Students do Exercises 3.2.6(c&d) and Exercise 3.1.3(b).

We introduce the product automaton which shows
that regular languages are closed under intersection
(Theorem 4.8).

We present a simple method for checking the
validity of laws for regular expressions (Section 3.4.63.4.7).

We point out that the above
method would fail if we add an intersection operator.
(though we saw that such an operator would make it easier to solve
say Exercise 3.1.1(a)).

We show that any DFA solving Exercise 2.2.5(b), generalized
to recognize strings where the k'th symbol from the right is a 1,
does need at least 2^k states.

12: February 19 (Wednesday)

With Exercise 4.4.1 as an illustrating example, we

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

show how to
use the equivalence classes to construct the minimal
DFA (Sect. 4.4.3)
Programming assignment 2 out.
Gradiance 7 due tonight.

13: February 21 (Friday)

Wrap up DFA minimization:

argue that the DFA resulting from minimization is indeed the
smallest possible (Sect. 4.4.4).

see that while a given language has a unique minimal DFA,
there may be several nonisomorphic NFAs of minimal size.
We observe (Section 4.2) that regular languages are
closed under many kinds of operations.
Motivated by a Gradiance assignment,
we discussed how to check that a given regular expression
does its job (cf. the upcoming programming assignment).

14: February 24 (Monday)


Student does Exercise 4.2.6(a).

Show that regular expressions are also closed under
reversal (Sect 4.2.2),
homomorphims (Sect 4.2.3), and inverse homomorphisms
(Sect 4.2.4).

Briefly discuss the complexity of various conversion/decision procedures
(Sect. 4.3).
Gradiance 8 due tonight.

15: February 26 (Wednesday)

We discuss (Section 4.1) how to prove
that a language is not regular;
a general technique that applies also to other
classes of languages is
the pumping lemma:

we apply it
(Exercise 4.1.1(a))

we show a situation where it cannot be applied
(Exercise 4.1.4(a)).
Students do Exercises 4.2.6(b,c).

16: February 28 (Friday)

We continue exploring the pumping lemma:

we prove it

students do Exercises 4.1.1(e) and 4.1.2(c)

we see how it can be applied to prove nonregularity of
the language of binary strings with different number of 0s and 1s
though other approaches are easier

we see another situation where it cannot be applied
(Exercise 4.1.4(b))
Assignment 3 due at 4pm.

17: March 3 (Monday)

Wrap up the first part of the course:

hand back graded Assignment 3

do Exercises 4.1.4(c) and 4.1.2(e)

mention Kozen's sound and complete axiomatization of
equivalence between regular expressions

discuss Programming Assignment 2, due next week
Gradiances 9 & 10 due tonight.

18: March 5 (Wednesday)

Exam I.

19: March 7 (Friday)

Introduce ContextFree Grammars (CFGs), cf.
Sections 5.1 & 5.2:

motivate how grammars are used in compilers

do Exercise 5.1.1(a), giving a CFG
for a nonregular language

do one part of the correctness proof:
that all strings generated by the CFG do indeed
belong to the language.
Student does Exercise 4.2.7.

20: March 10 (Monday)


We again look at Exercise 5.1.1(a),
and now prove that all strings in the language
are generated by the CFG.

We show
that the languages recognized by CFGs
include all regular languages

by converting a regular expression to a CFG (Exercise 5.1.3)

by converting a DFA to a CFG (Exercise 5.1.4(b))

Present a grammar for the language of binary strings
with exactly as many 0s as 1s
(cf. Exercise 5.1.8)
Gradiance 11 due tomorrow night.

21: March 12 (Wednesday)


Discuss and hand back graded Exam 1.

Discuss upcoming Programming Assignment 2.

Student proves that a given grammar
does indeed generate all binary strings
with as many 0s as 1s

Student does Exercise 5.1.1(d)

22: March 14 (Friday)


We present two grammars for strings of balanced (round and square)
parenthesis, cf. Exercise 5.3.2, and prove their equivalence.

We convert an ambiguous grammar for arithmetic expressions
into an equivalent but unambiguous grammar
(Sections 5.4.12).
Gradiance 12 due tonight.

March 1721

Spring break.

23: March 24 (Monday)


Student proposes another solution to Exercise 5.1.1(d)

Write a CFG for {w w^R}
and mention that {w w} is not contextfree
(we shall later write CFGs for the complements of these languages)

Mention that some grammars are inherently ambiguous (Section 5.4.4)

Show another source of ambiguity:
"if then (else)" constructs (cf. Exercise 5.4.1)
Programming assignment 2 due at 11pm.

24: March 26 (Wednesday)


Students write a grammar for the complement of {w w^R}

Students discuss how
to prove the correctness of their previous
solutions to Exercise 5.1.1(d)

We solve the ambiguity produced by
"if then (else)" constructs (cf. Exercise 5.4.3)

We sketch Exercise 5.4.2 which
gives an exact characterization of the strings generated
by the "ifthen(else)" grammar from last time.
Gradiance 13 due tonight.

25: March 28 (Friday)

Student writes grammar for the complement of
{w w}, cf. Exercise 5.1.1(c).
Embark on pushdown automata:

formally introduce the configurations, and the transitions
between them (Section 6.1)

mention the two kinds of conditions for accepting a string:
"final state" (Section 6.2.1) and
"empty stack" (Section 6.2.2)

illustrate by Exercise 6.2.1(a).
Gradiance 14 due tonight.

26: March 31 (Monday)

Continue pushdown automata:

student does Exercise 6.2.1(b)

prove that they accept exactly
the contextfree languages (Section 6.3),
by

showing how to convert a CFG into an equivalent PDA,
and

sketching how to convert a PDA into an equivalent CFG

27: April 2 (Wednesday)


Elaborate on how to convert a PDA into an equivalent CFG
(which may be further simplified,
thus motivating Section 7.1 on normalizing CFGs).

Discuss DPDAs (deterministic PDAs), cf Section 6.4.1

for the language {w w^R} (cf. Example 6.1/6.2),
nondeterminism is needed
(cf. the argument on top of p.255)

Show the equivalence between the two acceptance criteria for PDAs:

one can
convert a PDA that accepts by empty stack into one that accepts by final state
(Section 6.2.3);
this will preserve the property of being deterministic.

one can convert a PDA that accepts by final state
into one that accepts by empty stack
(Section 6.2.4);
this might lose the property of being deterministic
(since deterministic PDAs that accept by empty stack can only
recognize a very limited class of languages).
Assignment 4 due at 4pm.
Gradiance 15 due tomorrow night.

April 4 (Friday)

Class canceled (AllUniversity Open House)

28: April 7 (Monday)


Discuss and hand back graded Assignment 4

Student does Exercise 6.3.5(c)
Mention a hierarchy (cf. Sections 6.4.26.4.4):
deterministic PDAs accept
(by "final state")

strictly more languages than finitestate automata, but

strictly less languages than general PDAs (even some languages
with an unambiguous CFG cannot be accepted by a deterministic PDA).
Introduce the pumping lemma for CFGs (Section 7.2):

illustrate it by
Example 7.19

show why it cannot be applied to
a language that appears quite similar, cf. Exercise 7.2.2(b).

29: April 9 (Wednesday)

Continue the pumping lemma for contextfree languages:

students do Exercises 7.2.1(b&e)

we prove that {0^m 1^p 2^m 3^p} is not context free,
cf. Example 7.20, and understand why
the two "similar" languages can not
be proved noncontextfree
Discuss how to simplify a CFG (Section 7.1), by

removing useless symbols (nongenerating, nonreachable)

removing epsilon and unit productions

30: April 11 (Friday)

Further discuss how to simplify a CFG:

discuss the proper order of the 4 simplification steps from last time

introduce Chomsky Normal Form (Section 7.1.5)
Show that CFLs are closed under certain operations (Section 7.3)

but not under intersection and complement
Assignment 5 due at 4pm.
Gradiance 16 due tonight.

31: April 14 (Monday)


Hand back, and briefly discuss, graded Assignment 5.

Student does Exercise 7.1.5, on conversion to Chomsky Normal Form.

Sketch a proof of the pumping lemma for contextfree languages
(Theorem 7.18).

Show the limitations of the pumping lemma.
Gradiance 17 due tonight.

32: April 16 (Wednesday)

Exam II.

33: April 18 (Good Friday)


Sketch how Ogden's lemma (cf Exercise 7.2.3) can be used to prove that
{a^i b^j c^k  i,j,k different} is not contextfree.

Discuss why CFLs are not closed under intersection and complement
(Section 7.3.4).
Discuss
how to test, for a given grammar,
whether a string is generated by that grammar:

this can be done in linear time
if the grammar has a deterministic PDA

in the general case, this can be done in cubic time,
by the CYK algorithm (Section 7.4.4)
as illustrated by Exercise 7.4.3(b)
(along the way we also did Exercise 7.4.5)

34: April 21 (Monday)

We show that for a large class of grammars,
membership can be decided in linear time
(cf. notes uploaded on KState Online):

Illustrate the workings of an LR(1) automaton when parsing a string

Sketch how to construct an LR(1) automaton

35: April 23 (Wednesday)

Discuss the upcoming Assignment 6:

construct the first 5 states of the LR(1) parsing table.
Mention that for contextfree languages, not all problems are decidable
(Section 7.4.5);

this is unlike the situation for regular languages

and motivates the last part of the course where decidability
is studied.
Introduce the Turing machine (Section 8.2)

illustrate by Example 8.3 (Figure 8.10, cf. Exercise 8.2.1).
Gradiance 18 due tonight.

36: April 25 (Friday)

Continue Turing Machines:

Students do Exercises 8.2.2(b) and 8.2.2(c)

Introduce multitape machines (Section 8.4.1)
which for the above exercises allows us 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),
whose convenience is illustrated by Exercise 8.4.3(a)
but which can be simulated by deterministic Turing machines,
though probably not in polynomial time...

37: April 28 (Monday)

Finish Chapter 8 on Turing Machines:

Student does Exercise 8.3.2.

Mention that Turing machines and "standard computers"
can simulate each other (Section 8.6).

Mention the ChurchTuring thesis, and Turing's argument that his machine
can do everything a
(human) computer can do, cf.
Turing's original paper (pp 1921).

Introduce machines that are even simpler than the Turing
machine, yet have the same languagerecognition power
(Section 8.5).
Discuss and hand back graded Exam 2.
Assignment 6 due at 4pm.
Gradiance 19 due tomorrow night.

38: April 30 (Wednesday)

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

Introduce the
recursive languages (Sections 9.2.1&2) which
allow decision algorithms always returning yes or no,
unlike the
RE languages (defined in Section 8.2.5).

Show how to encode a Turing Machine as a binary string (Section 9.1.2).

Introduce the universal language which is
accepted by the universal Turing Machine
and thus is RE (Section 9.2.3).
Student does Exercise 8.5.1(a,b).

39: May 2 (Friday)

Finish Sections 9.1 & 9.2, summarizing last class and then

Introduce the "diagonalization language" (Section 9.1.3) and show that
it is not RE (Section 9.1.4)

Use the previous result to show that the
universal language is
not recursive since its complement is not even RE
(Section 9.2.4)
Student does Exercise 8.5.1(d).

40: May 5 (Monday)

Cover Section 9.3:

Formally introduce
the technique of reduction (Section 9.3.1):
if L1 can be reduced to L2
and L1 is nonrecursive (nonRE) then also L2 is nonrecursive (nonRE)

Introduce L_{ne}, the language of encoded Turing machines whose
language is nonempty, and show (Section 9.3.2)
that

L_{ne} is RE, by sketching a Turing machine that accepts it;

L_{ne} is not recursive, by reducing the universal language to L_{ne}.

State Rice's Theorem (Section 9.3.3): 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).
Hand back graded Assignment 6.

41: May 7 (Wednesday)

Wrap up Section 9.3:

students do Exercises 9.3.4(a,b)

do Exercise 9.3.6(a),
showing that some questions about Turing machines
are decidable.
Introduce PCP (Post's Correspondence Problem, Section 9.4)

which is about
"real things" (rather
than about Turing machines)

but is still undecidable

unless alphabet has only one symbol (cf. Exercise 9.4.3)
as can be shown by reducting L_u to PCP
Gradiance 20 due tonight.
Assignment 7 due tomorrow at noon.

42: May 9 (Friday)

Wrap up the course:

Discuss and hand back graded Assignment 7

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.
Gradiance 21 due tonight.

May 14 (Wednesday)

Final exam, 11:50am1:40pm
Torben Amtoft