CSC 385 - Formal Logic and Computation
2008 Spring Semester

This class covers the topics of a formal approach to logic and computation, including formal languages.

Essential Information:

Instructor:	Noel Petit
E-mail:	petit@augsburg.edu
Phone:	(612) 330-1061
Office:	Sverdrup 203D
Class:	Monday, Wednesday and Friday from 2:30 p.m. to 3:30 p.m. in Sverdrup 202
Dates:	14 January through 25 April, 2008
Text:	Discrete Structures, Logic, and Computability; Hein, 2nd Edition, Jones & Bartlett
Office Hours:	TBA

Grading

There will be two mid-term quizes, each counting for 15 percent, and a final exam counting for 30 percent of the grade. Graded homeworks will make up the remainder of the grade. All homeworks must be completed individually.

Schedule (Subject to change)

Date	Topics	Chapter
Week of 14 January	Intro, Basic Notions of Sets and Logic.	Hein Chapter 1
Week of 21 January	Elementary Logic	Hein Chapter 6
Week of 28 January	Predicate Logic	Hein Chapter 7
Week of 4 February	More Predicate Logic, Some PROLOG	Hein Chapter 7, 9.2
Week of 11 February	Regular Languages, Regular Expressions	Hein Chapter 11.1
Week of 18 February	Quiz, Finite Automata	Hein Chapter 11.2
Week of 25 February	DFAs and NFAs	Hein Chapter 11
Week of 3 March	Grammars and Using JFLAP	Hein Chapter 3.3
Week of 10 March	Regular Grammars and the Pumping Lemma	Hein Chapter 11.4
Week of 17 March	Mid-Semester Break	No Class
Week of 24 March	Context Free Languages and PDAs	Hein Chapter 12
Week of 31 March	Push-Down Automata	Hein Chapter 12
Week of 7 April	Turing Machines	Hein Chapter 13.1
Week of 14 April	Computational Models	Hein Chapter 13.2
Week of 21 April	Limits of Computability, Review	Hein Chapter 14

Assignments

Assignments will be due at the beginning of class on the day listed.

Assignment	Date Due
1.2: 2, 12, 18, 1.3: 8, 10	28 January, 2008
6.2: 10, 11, 14, 6.3: 5, 6	8 February 2008
7.3: 1, 6, 7, 8	13 February 2008
Prolog Exercises	15 February 2008
11.1: 1, 2, 5, 9	29 February 2008
11.2: 2, 4, 5, 6, 8	7 March 2008
3.3: 4, 5, 10, 11.4: 1, 6, 7d	26 March 2008
12.2: 1, 3, 7, 12.4: 4 Load ex5.5b and ex5.5c into JFLAP. List some strings that are accepted and not accepted. Determine the language represented.	11 April 2008
13.1: 2, 4, 6 Load ex9.5langacc-a and ex9.5langacc-b and describe the language which is accepted by each one. Correct the machine in ex9.5fix-a so that it accepts the language where each string has twice as many a's as b's. Load ex9.5trans-a and ex9.5trans-b and describe the function that each represents.	21 April 2008

Exam Schedule

The first quiz will be held on Monday 18 February. It will cover sets, propositional logic, and predicate logic.

The second quiz will be held on Friday 28 March. It will cover regular languages, regular grammars, regular expressions, DFAs and NFAs.

Class Links

In order to visualize and draw automata, you should use the JFLAP tool. The software comes as an executable jar file.