CIS510 Course Outline

Instructor:	Dr. Arthur T. Poe
Time:	Section 1: Wednesdays $4:40 – 7:10pm
Place:	Section 1: TL 305A
Text:	Denning, Dennis, and Qualitz : Machines, Languages, and Computations (Prentice Hall). Reprint
Pre-requisites:	2-semesters of Discrete Structures (CIS242 or CIS540)
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:	Floyd & Beigel: The Languages of Machines ( W.H.Freeman ) This book treats similar topics but takes a different approach
	Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages and Computation. (Addison Wesley) Taylor, R.G. : Models of Computation and Formal Languages.(oxford) Savage, J. : Models of Computation. (Addison Weslely)
	Other books on automata, languages, machines and computation: by D. Wood, by Sudkampt, by Brookshear, by Cohen, by Arbib, by Ginsburg, by Harrison, etc. Also Books on Compiler Design Books on Compiler Design: such as Lewis, P.M., Rosenkrantz, D.J., Stearns, R.E. Compiler Design Theory.
Grading:	Homework: 15-20%
	Midterm: 35 – 40 %
	Final: 40 -- 50%

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 assign and collect homework every week. These weekly homework are for you to do by yourself. Copying somebody else's work is prohibited. To better understand the course material, you are encouraged to “DISCUSS” with your classmates or to get help from me.

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. And if you miss final without a prior arrangement and agreement, your grade will be automatically an F.

My Office: 1008 Wachman Hall

Office Phone: 204-6481

Office Hours: Mondays

Tuesdays

Wednesdays

Email address: poe@temple.edu

Home Work is due and collected every week on the day of our lecture. Late homework will be at your own risk.

The Dean’s office asks us also to provide with the following information::

First day of School: Monday, August 28th, 2006

Last day to drop: Monday, September 11th

Last day to withdraw: Monday, October 30th

Thanksgiving Recess: Thursday, Novemeber 23 – Sunday November 26

Last day of Class: Wednesdays, Dec. 6th

Final Exam: Wednesday, Dec 13th

Outline
I. Preliminaries:	Recursive definition Principle of Mathematical Induction Relations: properties of a relation, Closures Functions: Bi-jection, 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 fa. 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