Updated 07/01/2004
262-417 (Summer 2004): Introduction to Theory of Computation
Instructor:
|
|
Place:
|
Monday & Wednesday EMS E295 09:30am-12:20pm
|
Office hours:
|
EMS E275, Mon & Wed 12:30pm-1:30pm
|
Introduction to formal languages, grammars and automata, finite state automata, pushdown automata, turing machines, regular languages, context-free, recursive and recursively enumerable languages, and Decidability.
Topics to be covered:
0.1 Automata, Computability, and Complexity
0.2 Mathematical Notions and Terminology
0.3 Definitions, Theorems, and Proofs
0.4 Types of Proof
1.1 Finite Automata
1.2 Nondeterminism
1.3 Regular Languages and Regular Expressions
1.4 Pumping Lemma and Nonregular Languages
2.1 Context-free Grammars
2.2 Pushdown Automata
2.3 Non-context-free Languages
3.1 Turing Machines
3.2 Variants of Turing Machines
3.3 The Definition of Algorithm
4.1 Decidable Languages
4.2 The Halting Problem
5.1 Reducibility
5.2 Simple Undecidable Problems
5.3 Mapping Reducibility
Suggested Problems & Supplementary Materials:
- SYLLABUS
- Midterm Exam is June 23, 2004 (in class)
- Final Exam is July 7, 2004 (in class)
- Suggested Problems Chapter 1:
1.1 , 1.2 , 1.3 , 1.4 (a,c,e,g,i,k,m) , 1.5 (b,d,f) , 1.12 (b) ,
1.13 (a,c,e,g,i,k,m) , 1.14 (a) , 1.15 (a,c,e,g) , 1.16 (a) ,
1.17 (b) corrected to A2 = { ww | w is a member of {a,b}* }
- Solution of Chap.1
- Suggested Problems Chapter 2:
2.1 (b,d) , 2.3 (a,c,d,g,i,k) , 2.4 (a,c,e,g) , 2.9
2.10 (show PDA that recognizes A) , 2.14 , 2.18 (b)
- Solution of Chap.2
- Suggested Problems Chapter 3:
3.1 (a,c) , 3.2 (a,c,e) , 3.6 , 3.8 (b) , 3.9
- Suggested Problems Chapter 4:
4.10 , 4.12 , 4.14 , 4.15
- Solution of Chap.3
- Solution of Chap.4
Computer Science @ UWM
University of Wisconsin-Milwaukee