## CS 330

Formal Methods and Models

Spring 2007

**Dr. D. Nordstrom**

361 Science and Tech II

dnordstr@gmu.edu

(703) 993-1565

Office Hours: Monday and Friday, 11:30 - 12:30, and Wednesday 6:00 -
7:00, and by appointment.
### Text

Henry Hamburger and Dana Richards, *Logic and Language Models for
Computer
Science*,
Prentice Hall, 2002.
### What You Should Know

The prerequisites for this course are C or better in CS 211 and Math
125. You
are expected to have a strong mathematical background and be able to
reason
abstractly. Programming skill is assumed and you should be comfortable
with C
or C++.

### The Course

In this course we will look at the mathematical logic which underlies
computer science, formal languages, and at abstactions which model the
processes of computation.

From logic we will discuss basic *propositional* and *predicate
logic* with application to validating programs. We will also have an
introduction to *logic programming* using the programming language
Prolog.

We will investigate *regular expressions* and *context-free
grammars*
as formal languages along with their relations to *finite automata*
and
*push-down automata*. In addition to the importance these subjects
have to
the theory of computer science they have applications to compiler writing
and
computer translation in general. We will use the programming tool Lex to
see
some practical application of regular expressions.

*Turing Machines* provide a formal model of computation. They are
used
to study, among other things, the limits of computation and complexity of
algorithms. We will become acquainted with fundamental ideas from this
area.

### Grading

There will be regular homework, programming assignments, a midterm and
a
final exam. No late homework will be accepted. Late programs will be
accepted
but with a five points (out of 100) per day late penalty. There will be
no
makeup exams except for extreme and well-justified (as judged by
me) cases.
Grades will be computed from a scored weighted by:

- Final exam 35%
- Midterm exam 30%
- Programs 20%
- Homework 15%