CIS510 Course Outline
Instructor: 

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 
Prerequisites: 
2semesters of Discrete Structures (CIS242 or CIS540) 
References: 
Hopcroft and Ullman: 

Lewis & Papadimitrious: 

Revesz, G.E. 
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: 1520% 

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 makeup 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: 2046481
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: 

II. Finite State Machines with output 

III. Finite Automata 

IV. Formal Grammars and Languages 

V. ContextFree (Type 2) languages 

VI. Contextsensitive Grammar 

VII. Turing Machine 
