State University of New York at Oswego



    

  1.  COURSE NUMBER AND CREDIT  
    2. 

    
        CSC 221 - 3 Semester Hours

    


  2.  COURSE TITLE 
    3. 

    
        Languages and Machines

    


  3.  COURSE DESCRIPTION 
    4. 

    
        This course provides students with a broad
        perspective of computer science and acquaints
        them with formal systems on which modern
        computer science is based.  Students study the
        structure and interpretation of three classes of
        abstract computing machines and their equivalent languages.

 

    


  4.  PREREQUISITES 
    5. 

    
CSC 212

    



  5.  COURSE JUSTIFICATION 
    6. 
 
    


    
        There is a need to provide students with a broad
        perspective of computer science, which they do not
        derive from any other single computer science course.
        There is a need to acquaint students with various
        formal systems on which modern computer science is
        based.  One section of this class will be taught each
        semester to classes of size thirty-two.  This course
        is required for CS majors.


    

  6.  COURSE OBJECTIVES 
    7. 
 
    
Upon successful completion of this course, students will be able to:

    

      

    1.  Demonstrate an understanding of logical and mathematical notation and 
            techniques
            in automata theory.

    2.  Demonstrate an understanding of regular expressions, regular languages, 
            and
            finite automata.

    3.  Show the equivalence between FAs and REs.

    4.  Demonstrate an understanding of context-free languages and pushdown 
            automata.

    5.  Show the equivalence between CFAs and PDAs.

    6.  Demonstrate an understanding of Turing machines.

    7.  Demonstrate an understanding of the Chomsky hierarchy.

    


    

  7.  COURSE OUTLINE 
    8. 

      

    1.  Mathematical Preliminaries
   
        
   
      1.  Basic Mathematical Objects:  sets, functions, logic and logical 
                statements,
                relations, functions, proofs, languages
   
      2.  Principle of Mathematical Induction, recursive definitions of 
                languages
    
      

    2.  Regular Languages and Finite Automata
   
        
   
      1.  Regular Expressions and Regular Languages
   
      2.  Finite Automata: deterministic and nondeterministic
   
      3.  Kleene's Theorem
   
      4.  Minimal finite automata
   
      5.  Regular and nonregular languages
   
      6.  The pumping lemma for regular languages
   
      

    3.  Context-free languages and pushdown automata
   
        
   
      1.   Context-free languages
   
      2.   Derivation trees and ambiguity
   
      3.   Pushdown automata
   
      4.   Equivalence of CFAs and PDAs
   
      5.   Non-context-free languages
   
      6.   The pumping lemma for context-free languages
  
      

    4.  Turing Machines
   
        
   
      1.  Models of Computation
   
      2.  Chomsky hierarchy
   
      3.  Variations of Turing Machines
   
      4.  Recursively enumerable languages
   
      5.  Unsolvable problems - The Halting Problem
   
      

    

    



  8.  METHODS OF INSTRUCTION 
    9. 

     

      

    1.          Lectures, discussion, and classroom demonstration.

    

    



  9.  COURSE REQUIREMENTS 
    10. 

     
        Assigned readings, homework, papers, and projects.

    


  10.  MEANS OF EVALUATION 
    11. 

    

      

    1.          Problem sets and examinations.

    


    


  11.  RESOURCES 
    12. 

    
        No additional resources needed.

    


  12.  BIBLIOGRAPHY 
    13. 


    

          J. Brookshear.  
          Theory of Computation:  
            Formal Languages, Automata, and Complexity. 
          Benjamin/Cummings, 
          New York, 
          1989.
          

    

          D.A. Cohen.
          Introduction to Computer Theory.
          John Wiley and Sons,
          New York,
          1996.
          

    

          R. Graham, D. Knuth, and  O. Patashnick.
          Concrete Mathematics.
          Addison-Wesley, 
          Reading, MA, 
          1989.
          


    

          W.K. Grassmann and J.-P. Tremblay.
          Logic and Discrete Mathematics:  
            A Computer Science Perspective.
          Prentice-Hall,
          New Jersey,
          1996.


    
          J.E. Hopcroft and J.D. Ullman.
           Introduction to Automata Theory, Languages, and Computation..
            Addison Wesley,
            New York,
            1979.



    

          D.C. Kozen.
          Automata and Computability.
          Springer-Verlag,
          New York,
          1997.    

    

          H.R. Lewis and C.H. Papadimitriou.  
           Elements of the Theory of Computation (2nd ed.).  
          Prentice-Hall, 
          New York, 
          1998.


    

          J.C. Martin
          Introduction to Languages and the Theory of Computation
          (2nd ed).
          Mc-Graw Hill,
          New York,
          1997.


    

          T.A. Sudkamp.
          Languages and Machines:  An Introduction to the Theory
            of Computer Science (2nd ed).
          Addison-Wesley,
          Massachusetts,
          1997.

    

 

    

    

 
 Document: 
    
 URL: 
    
 Last Update: