CIS 8513 Course Outline


" In Computer Science, Elegance Is Not A Dispensable Luxury, But A Matter Of Life And Death " 
                                                                --- E. W. Dijkstra
Instructor: Dr. Arthur T. Poe
Time: Tuesday, 4:40pm - 7:10pm
Place: Rm 322, Computer Activity Building
Text: Denning, Dennis, and Qualitz : Machines, Languages, and Computations (Prentice Hall).
Pre-requisites: 2-semesters of Discrete Structures (CIS 3242 or CIS 5503)
References: Hopcroft and Ullman:
Introduction to Automata Theory, Languages and Computations (Addison Wesley)
Lewis & Papadimitrious:
Elements of the Theory of Computation (Prentice Hall)
Revesz, G.E.
Introduction to Formal Languages (McGraw Hill)
Other References: Other books on automata, languages, machines and computation: by D. Wood, by Sudkamt, by Brookshear, by Cohen, by Arbib, by Ginsburg, by Harrison, etc.
Books on Compiler Design: such as Lewis, P.M., Rosenkrantz, D.J., Stearns, R.E. Compiler Design Theory (Addison Wesley)
A Recent Book by Flyod & Beigel : The Languages of Machines (W.H. Freeman) treats similar topics but takes an entirely different approach.
Grading: Homework: 25-30%
Midterm: 30%
Final: 40-45%

The text book explores the fundamental knowledge of three underlying themes of theory of computation: Abstract Machines, Languages and Computability. The course will try to give an integrated presentation of the results in these areas, showing their relations and equivalences. The development is formal but with an intuitive appeal. Most proofs are constructive in nature. The use of language theory concepts will have applications in engineering, compiler design, software specification, network protocol and complexity analysis.

I believe in active learning, namely learning is a two way street. Therefore, I encourage the class to ask questions. My answers, most of the time, will be another question --- a leading question. I expect you to read the course material we cover in class either before we meet in class or after class, PREFERABLY BOTH.

I collect homework every week. You are encouraged to DISCUSS with your classmates about course materials, homework etc, or to get help from me. Copying somebody else's work is prohibited.

I do not give make-up exam. If you have legitimate excuse, AND you obtained my prior approval, your course grade then will depend on homework and final.

Outline
I. Preliminaries:
  • Recursive definition
  • Principle of Mathematical Induction
  • Relations: properties of a relation, Closures of a relation
  • Functions: Bijection, Invertible Functions
  • Cardinality: Denumerable and non-denumerable sets
    Existence of Non-computable functions
  • Equivalence Relations and Partitions on a set
  • Algebraic Systems, Congruence Relations, Quotient Algebras
    and homomorphism, Direct Products
  • Strings, operations and relations on strings
    Solution to regular equation X = A X + B
  • Pigeon-hole principle
II. Finite State Machines with output
  • State Equivalence, Machine Simulation
  • Machine Minimization, Equivalence and their algorithms
  • Equivalence of Mealy and Moore Models
  • Functions that are computable by finite state machines with output
III. Finite Automata
  • Minimization of f.a.
  • Regular expressions and regular languages
  • Non-deterministic vs deterministic machines
  • Direct Product and Direct Sum of Machines
  • Regular Expression, and Kleene's Theorem
    set system equations(linear regular equations)
  • Closure properties of regular languages
  • Myhill-Nerode Theorem. Semigroup of an Automata
  • Pumping Theorem of regular languages
  • Decidable questions for regular languages
IV. Formal Grammars and Languages
  • Chomsky's characterization of type 0, 1,2,3 grammars and Languages
  • Derivation and left-most derivation
  • Derivation tree
  • Finite Automata and Regular languages
V. Context-Free (Type 2) languages
  • Transformation of grammar
  • Chomsky Normal Form
  • Pumping Theorem for cfl, Decidable question for cfl
  • Closure properties of cfl
  • Left-recursive and right-recursive variable
  • Greibach Normal Form
  • Self-embedding property, Ambiguity
  • CYK - membership algorithm
  • Push-down Automata, various notions of acceptance
  • Mirror language with center marker and Mirror Language
  • Equivalence of pda and context free grammars
VI. Context-sensitive Grammar
and Languages
  • Equivalence of cs vs length non-decreasing rules
  • Kroda Normal Form
  • One-sided context sensitive grammars
  • Linear bounded automata
VII. Turing Machine
  • Definition, computing with Turing machines
  • Church's Thesis
  • Universal Turing Machine
  • The Halting Problem
  • Word Problem and Post's Correspondence Problem
  • Unsolvable problems about grammars