COT 4420
Formal Languages and Automata Theory (3242/01S)
Last Update: 10 May 2001 by R.Levow
New or updated items
Note on final grade calculation
Text
An Introduction to Formal Languages and Automata by P. Linz,
3rd Edition, Jones and Bartlett Publishers, 2001
Objectives
The primary objective of the course is the development of an understanding
of the theoretical foundations of computer science. The two principle themes
are the relationships among languages, grammars, and model computational
devices; and the theoretical limits on computational devices. Students
will be expected to exhibit their understanding of these topics through
an understanding of the definitions of the formal objects of study, through
the ability to exhibit formal proofs of theorems in the domain of study,
and through the ability to apply theoretical results to specific concrete
problems including the coding of certain algorithms.
It is anticipated that the material in the chapters 1 through 12 of
the text will be covered except the starred sections, 1.3, 2.4, 6.3, and
7.4. This covers the following major topics.
-
Deterministic and Nondeterministic Finite Automata
-
Regular Languages and Regular Grammars
-
Properties of Regular Languages
-
Context-Free Language
-
Simplification of Context-Free Grammars and Normal Forms
-
Pushdown Automata
-
Properties of Context-Free Languages
-
Turing Machines
-
Other Models of Turing Machines
-
A Hierarchy of Formal Languages and Automata
-
Limits of Algorithmic Computation including the Halting Problem
Prerequisites
Students are expected to have a good grasp of discrete mathematics on entry
to the course. In particular, knowledge of the following areas is assumed:
basic set theory; functions, relations, and their properties; basic characteristics
of graphs and trees; basic proof techniques including mathematical induction.
Programming skills corresponding to a grade of C or better in Foundations
of Computer Science are assumed.
Assignments, Exams and Grading
Problem lists will be provided from time to time. You should study these
problems to be sure you can do each of them. Some of these problems will
be assigned as homework and many problems on the exams will be drawn from
the problem lists. A limited number of small programming assignments will
also be given. Each homework assignment will have a specified due date
and penalties will be assessed for late submission.
Follow this link for general
information on course policies including homework and program submission,
late penalties, getting help, etc.
There will be three exams. The each exam
will emphasize material not covered on previous exams but the final exam
will be comprehensive. In computing the final grade,
homework will count 25%, the first
exam on Feb. 27 will count 25%, the second
exam 20%, and the final exam on Thursday,
May 3, 35%. If only part 1 of the final exam is taken, the weights
of the three exams will be 32%, 26%, and 22%, respectively. (Note:
The weights total 105%. Grades will be scaled to a 0 - 100 range
by dividing by 1.05. Ten point intervals will be used with grades
between x7.0 and x9.9 receiving a '+' and those between x0.0 and x2.9 receiving
a '-'.)
Programming Assignments
Homework Assignments
General: Know how to do all problems for which
solutions are given in the book unless otherwise indicated. Do not
turn in these problems.
Work and turn in the problems listed below.
Problems must be submitted by the start of class on the date due.
Solutions will be discussed in class and no credit will be given for late
work on a problem that has been discussed.
-
Chapter 2: Sec. 1: 6, 7b, 9b, 18 (this must be a
dfa); Sec. 2: 3, 9a; Sec. 3-4 (No exercises) - Due 2/13
-
Chapter 3: Sec. 1: 7, 15a, 18b; Sec. 2: 1, 19 (Do
not do exercises 4 - 18), Sec. 3: 1, 5, (13 or 14) - Due 2/15
-
Chapter 4: No problems to turn in
-
Chapter 5: Sec. 1: 3, 12c; Sec. 2: 8 - Due 3/20