William Paterson University of New Jersey

Department of Computer Science
College of Science and Health

Course Outline

 

 

1.        TITLE OF COURSE AND COURSE NUMBER: Theory of Computation,   CS 445

           Credits: 3

 

2.        DESCRIPTION OF THE COURSE: This course investigates formal machine models of computation, formal languages, and computability. This includes finite state automata, pushdown automata, Turing machines, languages, and grammars and how they are useful within Computer Science.

 

3.        COURSE PREREQUISITES: CS 342 with a grade of C- of better

 

4.        COURSE OBJECTIVES:

 

To understand the historical and philosophical importance of the questions and results in Theory of Computation.

 

To understand the formal machine models created to investigate the limits of computation.

 

To understand the applications of the formal models and results to other areas of Computer Science.

    

5.        STUDENT LEARNING OUTCOMES:

 

           Upon completion of this course, students will be able to:

 

           a) Appreciate the historical development of theory of computation.

           b) Explain and apply the models of computation (finite automata, push downs, and Turing           

               machine equivalents) developed in class.

           c) Describe the relationship between languages and the computational models.

           d) Appreciate the application of the theory of computation to areas of computer science.

           e) Apply theory of computation results to computer science activities.

           f) Develop constructive proofs.

 

           Measure (for assessment of above outcomes): exams, surveys, and projects..

Through classroom participation and discussion, and various homework assignments, the course also reinforces the following student learning outcomes of the university:

 

 

a) Effectively express themselves in written and oral form. Measure: exams and projects.

b) Demonstrate ability to think critically.  Measure: exams and projects.

c) Demonstrate ability to integrate knowledge and idea in a coherent and meaningful
    manner.    Measure: exams and projects.

 

6.        TOPICAL OUTLINE OF THE COURSE CONTENT:

 

           Topic 1:         Review of Mathematical Foundations

 

           Topic 2:         Grammars

                                a)  Regular grammars

                                b)  Context-free grammars

                                c)  Context-sensitive grammars

                                d)  Chomsky Hierarchy of grammars

           Topic 3:         Regular languages

                                a)  Regular expressions

                                b)  Pumping Lemma

 

           Topic 4:         Finite automata

                                a)   Transition graphs

                                b)   Kleene's Theorem

                                c)   Non-determinism

                                d)   Output - equivalency of Moore and Mealy Machines

                                e)   Decidability

    

           Topic 5:         Context-free languages

 

Topic 6:         Pushdown automata

                                a)  Deterministic and non-deterministic

                                b)  Equivalency

                                c)  Decidability

 

           Topic 7:         Turing Machines

                                a)  Recursive and recursively enumerable languages

                                b)  Other formulations of computability

                                c)  Church's Thesis

                                d)  Decidability

 

7.        GUIDELINES/SUGGESTIONS FOR TEACHING METHODS AND STUDENT LEARNING ACTIVITIES:

          

           a)  Classroom lectures and discussions.

           b)  Homework reviews.

           c)  Pre-examination reviews

 

8.        GUIDELINES/SUGGESTIONS FOR METHODS OF STUDENT ASSESSMENT (STUDENT LEARNING OUTCOMES):

 

           a)  Periodic exams including final exam

b)  Regular homework practicing techniques and models covered in lecture.

 

 

9.        SUGGESTED READINGS, TEXTS, OBJECTS OF STUDY:

 

           Cohen, Daniel, 1996, Introduction to Computer Theory, (2nd Edition),  Wiley.

 

           Handouts and software such as  JFLAP and TM simulators.

 

 

10.      BIBLIOGRAPHICAL OF SUPPORTIVE TEXTS AND OTHER MATERIALS:

 

           Martin, John,  2003, Introduction to Languages and the Theory of Computation, (3^rd

           Edition), Mc Graw-Hill.

 

Mitkov, Ruslan,  2003, Oxford Handbook of Computational Linguistics,  Oxford University Press. 

 

           Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman,  2000, Introduction to

           Automata Theory, Languages, and Computation, (2nd Edition), Addison Wesley.

 

           Kozen, Dexter,  1999,  Automata and Computability, Springer Verlag.

 

           Greenlaw, Raymond, and H. James Hoover, 1998, Fundamentals of the Theory of

           Computation, Morgan Kaufman. 

 

           Kelley, Dean, 1998, Automata and Formal Languages: An Introduction, Prentice Hall.

 

           Lewis, Harry R.  and Christos H. Papadimitriou, 1997,   Elements of the Theory of

           Computation, (2nd Edition), Prentice Hall.

 

           Taylor, Ralph Gregory,  1997, Models of Computation and Formal Languages,

Oxford University Press.  

 

           Sipser, Michael,  1996,  Introduction to the Theory of Computation, Course Technology.

 

           Sigal, Ron , and Elaine J. Weyuker,  1994, Computability, Complexity, and Languages:

           Fundamentals of Theoretical Computer Science, (2^nd Edition), Academic Press.

 

           Martin, Davis and Weyuker, Elaine, 1989, Logic Language Constructs, Academic Press.

 

           Wood, D.,  1988,  Theory of Computation,  Wiley.

 

           Lewis, Harry and Papadimitriori, Christos, 1981, Elements of the Theory     of Computation, Prentice Hall.

 

11.      PREPARER'S NAME AND DATE: Dr. G. Ndjatou and J. Najarian, Spring 1996

12.      ORIGINAL DEPARTMENTAL APPROVAL DATE: Spring 1996

13.      REVISERS' NAME AND DATE: Dr. G. Ndjatou and J. Najarian,  Spring 2005,
and previously February 2000

14.      DEPARTMENTAL REVISION APPROVAL DATE: Spring, 2005