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:	Monday, Wednesday and Friday from 2:30 p.m. to 3:30 p.m. in Sverdrup 202
Dates:	17 January through 27 April, 2007
Text:	Discrete Structures, Logic, and Computability; Hein
Office Hours:	Monday, Wednesday and Friday from 1:00 p.m. to 2:30 p.m.

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 17 January	Intro, Basic Notions of Sets and Logic.	Hein Chapter 1
Week of 22 January	Elementary Logic	Hein Chapter 6
Week of 29 January	Predicate Logic	Hein Chapter 7
Week of 5 February	More Predicate Logic, Some PROLOG	Hein Chapter 7, 9.2
Week of 12 February	Regular Languages, Regular Expressions	Hein Chapter 11.1
Week of 19 February	Quiz, Finite Automata	Hein Chapter 11.2
Week of 26 February	DFAs and NFAs	Hein Chapter 11
Week of 5 March	Grammars and Using JFLAP	Hein Chapter 3.3
Week of 12 March NO CLASS ON 16 MARCH	Regular Grammars and the Pumping Lemma	Hein Chapter 11.4
Week of 26 March	Context Free Languages and PDAs	Hein Chapter 12
Week of 2 April	Push-Down Automata	Hein Chapter 12
Week of 9 April	Turing Machines	Hein Chapter 13.1
Week of 16 April	Computational Models	Hein Chapter 13.2
Week of 23 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	26 January, 2007
6.2: 10, 11, 14, 6.3: 5, 6	2 February 2007
7.3: 1, 6, 7, 8	12 February 2007
Prolog Exercises	16 February 2007
11.1: 1, 2, 5, 9	28 February 2007
11.2: 2, 4, 5, 6, 8	9 March 2007
3.3: 4, 5, 10, 11.4: 1, 6, 7d	26 March 2007
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 2007
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.	20 April 2007

Exam Schedule

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

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

The final will be held on Wednesday 2 May from 1:00 pm to 3:00 pm in Sverdrup 202.

Class Links

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