CIS 3211 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 & Thursday, 11:40am - 1:00pm
Place:  
Text: Daniel I. A. Cohen : Introduction to Computer Theory, 2nd Edition (Wiley).
Pre-requisites: CIS 1066, CIS 2166 or equivalent and consent of instructor
Other References: Thomas Sudkamp:
Languages and Machines (Addison Wesley)
  Peter Linz:
An Introduction To Formal Languages and Automata, (Jones and Barlett Publisher)
  Carroll and Long:
Theory of Finite Automata with an Introduction to Formal Languages (Prentice Hall)
  Vladmmir Drobot:
Formal Languages and Automata Theory (Computer Science Press)
Grading: Homework: 25-30%
  Midterm: 30%
  Final: 40-45%


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
PART I. FINITE AUTOMATA
I. Preliminaries: Chapter 1. Preliminary
  • Principle of Mathematical Induction
  • Cardinality, countable and non-countable sets
  • Recursive Definition
  • Equivalence Relations
  • Congruence Relation
  • Homomorphism, Isomorphismm
  • Backus-Naur Form
Chapter 2. Languages
  • Alphabet, strings, launguages, reverse of a string, concatenation of strings
  • Product of two languages
  • Kleen Closure
II. Finite Specification of Languages Chapter 3. Recursive Definitions
  • Another to define languages
  • Arithmetic expressions
Chapter 4. Regular Expression
  • The set of regular expressions
  • Languages associated with regular expressions
  • Understanding Regular Expressions
  • the Language of EVEN-EVEN
III. Automata & Their Languages Chapter 5. Finite Automata and Their Languages
  • Another way to define languages
  • Finite Automata
  • Languages Accepted by Finite Automata
  • EVEN-EVEN revisited
Chapter 6. Transition Graphs
  • Relaxing the restriction on inputs
  • Transition graphs and generalized transition graphs
  • Non-determinism
Chapter 7. Kleene’s Theorem
  • Converting Transition graphs into Regular Expressions
  • Converting regular expressions into f.a.’s
  • Non-deterministic Finite Automata (nfa)
IV. Mealy and Moore Machines Chapter 8. Finite Automata with Output
  • Moore machines, Mealy machines and their equivalence
  • The implementation of automata using memory devices (flip-flop)
V. Properties of Regular Languages Chapter 9. Regular Languages
  • Closure properties of regular languages
Chapter 10. Non-regular Languages
  • The Pumping Lemma for regular languages
  • The Myhill-Nerode Theorem
Chapter 11. Decidability
  • Equivalence problem
  • Empty Language Problem
  • Finite and infinite language
PART II. PUSHDOWN AUTOMATA THEORY
VI. Context Free Grammar and Context Free Languages Chapter 12. Context Free Grammar
  • Another to define languages
  • Context Free Grammar
  • Parsing tree and derivation tree
Chapter 13. Grammatical Format
  • cfg with and without null productions
  • Getting rid of unit productions
  • Chomsky Normal Form
  • Left-most derivation
Chapter 14. Pushdown Automata
Chapter 15. CFG = PDA
VII. Properties of cfl Chapter 16. Non-Context-Free Languages
  • Pumping Theorem for cfl
Chapter 17. Context Free Languages
  • Closure Porperties
Chapter 18. Decidability
  • Emptiness questions
  • Uselessness questions
  • Finiteness questions
  • Membership questions
PART III. Turing Theory
VIII. Turing Theory Machines with more computing power, Turing Machines, Post Normal Systems, 2pda, the Halting Problem for Turing Machines, a Universal Machine, Church-Turing thesis
Chapter 20. Turing Machines
Chapter 21. Post Machines
Chapter 22. Minsky’s Theorem (2pda)
Chapter 23. Variation on the TM
Chapter 24. Chomsky Hierarchy
Chapter 25. Computers