TDDA89 SLIDES
[Some of the files exist in other formats in the same
directory.]
-
An example
DFA
used in lecture 2.
-
NFA's with epsilon transitions
[PDF],
[PS, 4 per
page].
-
Regular expressions (hand-written, thanks for scanning and for shrinking the
file size!)
[
PDF, 1.2 MB],
[
PDF, 7 MB].
-
From finite automata to regular expressions
[PDF],
[PS, 2
per page].
What is presented here is based on Dean Kelley, "Automata and formal
languages: an introduction", Prentice-Hall, 1995, pages 62-64.
-
A brief overview of Myhill-Nerode theorem
[PDF],
[PDF, 2 per page]
and a slide on equivalence relations
[PDF].
-
The pumping lemma for regular languages (hand-written, thanks for scanning!)
[here].
-
Parse trees and ambiguity (Lecture 7)
[PDF].
-
Removing left recursion (Lecture 8)
[PDF],
[PDF, 4 per page].
-
Constructing a PDA for a given CFG.
[PDF],
[PDF,
4 per page].
-
LL(1) parsing
[PDF].
-
Introduction to LR(0) parsing
[PDF],
[PDF,
2 per page]
-
Definition of an LR(0) grammar¹
[PS,
2 per page],
[PDF,
2 per page].
-
Handwritten slides used at the lecture on LR(0) parsing (thanks for scanning!)
[here].
-
Definition of an LR(1) grammar
[PS]
[PDF]
and
[PDF].
-
An example Turing machine
[PS]
[PDF].
-
Decidable and undecidable problems (Lecture 15, 16)
[PS, 4
per page],
[PDF].
.
¹ Comment: Our definition of LR(0) grammars is simpler
but slightly less general than that in the book [Hopcroft&Ullman].
The definitions differ only for some particular grammars. An example is
{ S->Ab, A->epsilon, A->Aa }.
(A grammar satisfying only the more general definition must contain an
epsilon production and no other production for the same symbol has the right
hand side beginning with a terminal.)
[2006.07.05]
