HW3: Chapter 1, Problem 34, 42, 43. DUE: Feb 18.

HW4: Chapter 3, Problem 5, 12, 45, 46,

HW5: Chapter 5, Problem 2 just give the noncontracting form,

HW6: Chapter 16, Problem 3, 4, 9a, 11 (don't do the sentential form). DUE March 20.

HW7: Chapter 6, Problem 34, 29, 30, 39, 40. On problem 34, just go from NDFA to DFA. On problem 29 and 30, lambda-NDFA to NDFA. On problem 39 and 40, just construct the minimal DFA. DUE March 31.

HW8: Chapter 7, Problem 11a, 11b, 11d. Chapter 8, Problem 3a, 3b, 3c. DUE April 7.

LAB ASSIGNMENT:

LAB SUBMISSION:

1. Convert your files(s) to a 'tar' file. Use the command:

>>>	tar -cvf somename.tar files

For example to tar the files num1.java and num2.java we would write:

>>>	tar -cvf student-name.tar *.java

2. Use the checkin program located at ~simmonds/bin/turnin to submit your tar files, for example:

>>>	~simmonds/bin/turnin student-name.tar

Lectures

• LECTURE SET 1 PDF and Postscript
• LECTURE SET 2 PDF and Postscript
• LECTURE SET 3 PDF and Postscript
• LECTURE SET 4 PDF and Postscript
• LECTURE SET 5a PDF and Postscript
• LECTURE SET 5b on Parsing PDF and Postscript
• LECTURE SET 5c on LL(k) PDF and Postscript
• LECTURE SET 6 PDF and Postscript
• LECTURE SET 7 PDF and Postscript
• LECTURE SET 8 PDF and Postscript
• LECTURE SET 9 PDF and Postscript
• LECTURE SET 10 PDF and Postscript
• LECTURE SET 11 PDF and Postscript
• LECTURE SET 12 PDF and Postscript
• LECTURE SET 13 PDF and Postscript
• LECTURE SET 14 PDF and Postscript
• LECTURE SET 15 PDF and Postscript
• KNAPSACK PDF and Postscript

  Description:

  You will learn how to study computation in terms of abstract language and machine models. These include formal languages, finite state automata, pushdown automata, Turing machines. Parsing and syntactic correctness will also be covered.

  Prerequisites: CS166, CS200, knowledge of discrete mathematics; Java, C or C++.

  

  Logistics

  When and Where:	MW 12:10-1:00PM	118 Sheppard
  When and Where:	TTh 12:10-1:00PM	133 Wagar
  Instructor:	Darrell Whitley	whitley@cs.colostate.edu
  	University Services 227	970-491-5373
  Office Hours:	Monday 1:30-2:30, Tuesday 2:30-3:30
  GTA:	Devon Simmonds	ta@cs.colostate.edu
  Office Hours:	4 to 6 on Tuesday in the NORTH LAB

  

  Text:

  • Thomas Sudcamp, Languages and Machines , Addison-Wesley, 1997, second edition.

  Grading:

  quiz I	Date?	7%
  Midterm I	March 4	30%
  Homework		11%
  Labs		14%
  Midterm II	April 24	30%
  quiz II	May 6	8%
  Final Exam	Monday, May 12, 9:10-11:10	25%

  Note that the 2 quizes, 2 Midterms and the Assignments total 100 points. The Final is optional. If the Final is taken, then your pre-final score will equal 75 percent of the total points.

  Each assignment must be submitted at the beginning of the class on the given deadline for that assignment. No late work will be accepted. If you miss more than 1 quiz or exam you will receive a zero.

  You may discuss assignments, but make sure you do your own work. Please read the departmental policy statement regarding incompletes, cheating, and class attendance. This policy statement is in the file student info. Cheating will result in an automatic F in this class.