Term: Spring 1998

University Course Number: Math 485/CS 490

Course Title: Theory of Computation

Instructor: Erol Barbut, Professor of Mathematics

e-mail: ebarbut@uidaho.edu

Phone: (208) 885-6742

Textbook: Introduction to Languages and Theory of Computation, Second edition

John C. Martin -- McGraw Hill, 1996
ISBN 0-07-040845-9

Outside reading/references:
  Introduction to the Theory of Computation by Michael Sipser -- pub.PWS Publishing Co. Introduction to Automata Theory, Languages and Computation by J. E. Hopcroft and J. D. Ullman -- pub. Addison Wesley The Theory of Parsing, Translation and Compiling, Volume I: Parsing by A.V. Aho and J. D. Ullman -- pub. Prentice Hall

Homework: There will be 5 problem sets. Each problem set will be worth 10 points. These problem sets are indicated on the tape schedule, and are due upon receipt of the tapes, indicated by the remark "HW#x".

Tests: There will be three 50 minute exams. Each of these will be worth 100 points. In addition, there will be a two hour final exam. The final exam will be worth 200 points.

Grading: Your grade will be based on a total of 550 points. The letter grade you receive will be determined relative to the class average, with the class average counting as a B-.

HW#1: 1.1(a,b,d),1.3(b),(c),1.5(b),1.6(e),1.21(a),(b),1.27,2.3,2.19
   1          Sets, Functions                  1.1,1.3
   2          Relations                          1.4
   3          Languages                          1.5
   4          Proofs                             2.1
   5          Mathematical Induction           2.2,2.3
   6          Recursive Definitions              2.4
   7  HW#1    Regular Languages and Expressions  3.1
HW#2: 3.1(b),3.5,3.9(d),3.23 (a),(d),(e),3.24,3.25
   8          Finite Automata                    3.3
   9             "      "                        3.3
   10            "      "                      3.3,3.4 (Another example)
   11            "      "                        3.5
   12            "      "                      3.4,3.5
       13 HW#2    Nondeterministic FAs(FTP site for FA software Also check
http://www.cse.ogi.edu/~kxf/Simulator.html for a Java applet to build and
simulate a finite state automaton.)              4.1
HW#3: 4.1(a,b),4.8,4.9,4.14(e),4.21(a,b,e),4.22(a,b),4.31(b,d)
   14         Nondeterministic FAs                4.1   
   15                 "         "              4.1,4.2
   16                 "         "                4.2
   17                Review
   18               Exam 1
   19         Kleene's Theorem                   4.3
   20            "       "                       4.3
   21         Criteria for Regularity            5.1
   22 HW#3        "           "                  5.3
HW#4: 5.4,5.6,5.27(a,c,f),5.30,5.35(a,f),6.1(a,c,f),5.3
   23         Context-Free Languages             6.1
   24            "      "      "                 6.1
   25            "      "      "               6.2,6.3
   26            "      "      "                 6.3
   27         Derivation Trees and Ambiguity     6.4
   28 HW#4           R e v i e w
HW#5: 6.6,6.17(b,d,e),6.19(a,d),6.22,6.35(a,b),6.36(c),6.43(a),7.5(f),7.6
   29                  Exam 2
   30         Simplified and Normal Forms        6.6
   31           "       "                        6.6
   32             Chomsky Normal Form            6.6
   33             Pushdown Automata              7.1
   34             "      "                       7.2
   35             "      "                       7.3
   36         CFLs and Non CFLs                  8.1
   37          "    "   "    "                   8.1
   38 HW#5     "    "   "    "                   8.2
   39         Turing Machines                  9.1,9.2
   40               R e v i e w
   41                 Exam 3
   42         Recursively Enumerable Languages 10.1,10.2
   43                "       "            "      10.3
   44                R e v i e w