Text Only VersionSkip to global navigationSkip to section navigationSkip to page body
 

 

Syllabus for CIS 510

CIS510 Course Outline

none

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%

none


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