CSE 322: Introduction to Formal Models in Computer Science
Winter 1998
Syllabus

Paul Beame

TA: Jong Hee Kang

Communication with the instructor and TA by email is encouraged.

Text Book

Michael Sipser, Intro. to the Theory of Computation, PWS Publishing, 1997. First Edition. There is a soft-cover Preliminary Edition of this text that is not complete. It may be adequate for you but a number of examples and exercises will be missing so it will be inconvenient to use.

Grading:

The course grade will be based on homework, a midterm, and a final exam. The approximate weighting of the three components is 40-50% Homework, 15-25% midterm and 30-40% final exam.

Homework:

Homework is intended to be a major portion of the course. Assignments will be due weekly, usually on Friday. It is expected that homework solutions represent original work.

Course Web:

All the CSE 322 handouts will be available on the department's course web: Document URL http://www.cs.washington.edu/education/courses/322. The subdirectories contain copies of handouts from previous offerings of the course (including old exams).

Midterm

February 11 or 13 in class

Final Exam

Tuesday March 17, 2:30-4:20 in class

Topics:

We will cover all of Part I of the textbook in detail and will supplement it from time to time. We will also very briefly survey later material.

Course Goals: 

Preconditions and Postconditions for CSE 322

CSE 322: Introduction to Formal Models in Computer Science

Purpose:

Languages, finite automata, regular expressions, context-free grammars, 
and other automata such as pushdown store machines and Turing machines.
Introduction to proofs and theoretical concepts such as nondeterminism.

Precondition Concepts:
  discrete structures
    basic set theory
    relations
    graphs
    recursive definitions
    proof techniques
  programming languages
    simple parsing ideas
    syntax of programs

Precondition Abilities:
  read and understand elementary mathematical proofs
  design simple proofs
  design recursive defintions

Precondition Skills:
  write mathematical expressions
  use algebra with facility

Postcondition Concepts:

  strings and Languages
    concatenation, powers, and reversal of strings
    operations on languages, union, concatenation and star
  regular languages
    regular expressions 
    countability of the regular languages
    countability and uncountability, (Cantor's proof)
  context-free grammars 
    examples from real programming languages such as C++
    derivation trees
    leftmost and rightmost derivations
    ambiguous grammars
    inherently ambiguous context-free grammars
    non-context-free languages w/o proof
    closure Properties - union, concatenation, star
    decision problems - emptiness, finiteness, equivalence
  parsing methods 
    top-down and bottom-up parsing 
    deterministic and non-deterministic parsing
  finite automata 
    DFA's
    NFA's
    equivalence of NFA's and regular grammars
    subset construction
    Kleene's theorem
    closure properties - emptiness, finiteness, equivalence
    decision problems
    cross product construction
    nonregular languages
  pushdown automata
    deterministic PDA's
    top-down and bottom-up constructions PDA's from context-free grammars
    relationship between ambiguity in grammars and nondeterminism in PDA's
  Turing machines
    universal Turing machine
    halting problem is undecidable

Postcondition Abilities:
  design a regular expression, finite automaton, or context-free grammar for
     a given language
  parse strings given a context-free grammar
  prove simple facts about regular expressions, finite automata, and 
     context-free grammars
  identify undecidable problems related to programming

Postcondition Skills:
   better write mathematical expressions
   better prove simple facts

(Last Update: 01/14/98 )