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

Essential Information:

Instructor:	Erik Steinmetz
E-mail:	steinmee@augsburg.edu
Phone:	(612) 330-1062
Office:	Sverdrup 203A
Class:	6:00 p.m. to 10:00 p.m. in Sverdrup 206
Dates:	30 March, 13 April, 27 April, 11 May, 18 May, 1 June, 15 June
Text:	Discrete Structures, Logic, and Computability; Hein
Office Hours:	Monday evenings in my office or Sverdrup 206 from 6 p.m. to at least 7 p.m. Dates: 9 April, 23 April, 7 May, 14 May, and 11 June.

Grading

There will be a mid-term and a final exam during the course, each 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
30 March	Sets, Languages, and Propositional Logic	Hein 1, 6
13 April	Predicate Logic	Hein 7
27 April	Verification and Logic Programming, Grammars	Hein 9, 3.3
11 May	Review, Mid-term, Regular Expressions	Hein 11.1
18 May	Finite Automata, Regular Languages	Hein 11.2, 11.3, 11.4
1 June	Context-free Languages, Pushdown Automata, Turing Machines	Hein 12, 13
15 June	Completeness and all that, Review, Final	Hein 14

Assignments

Assignments will be due at the beginning of class on the day listed. No late work will receive credit, as we will go over some of the problems in class.

Assignment	Date Due
1.2: 2, 12, 18; 1.3: 8, 10; 6.2: 10, 11, 14, 6.3: 5, 6	13 April
7.2: 8, 10; 7.3: 1, 6, 7, 8	27 April
Prolog: using only parent, spouse, male and female predicates, create rules for mother, grandmother, father, grandparent, child, grandchild, descendent, wife, husband, aunt (both ways).    3.3: 4, 5, 10	11 May
11.1: 1, 2, 5, 9	18 May
11.2: 2, 4, 5, 6, 8; 11.4: 1, 6, 7d	1 June
12.2: 1, 3, 7; 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.	15 June

Exam Schedule

The mid-term will be held during the middle 90 minutes of class on 11 May.

The final will be held during the final 120 minutes of class on 15 June.

Class Links

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