The course meeting time is 12:30MW and 9:00Th in Dunn 111. The text for the course is "Introduction to the Theory of Computation", Second Edition, by Michael Sipser. We will cover Chapters 1-5 and parts of 6, 7 and 9.
Grades will be assigned with approximately the following weights:
Check this URL regularly for information about the course.
An on-line text on similar material is http://www.cs.uky.edu/~lewis/educ.html
From the text: 0.2 b,c,e,f, 0.6, 0.7, 0.11; 1.4 a,e,g, 1.6 a,b,e,i,
Due in class: September 18.
From the text: Chapter 1: 1.5 d,e; 1.7 c,e; 1.10 b; 1.14 b; 1.16 b
Due in class: September 25.
NOTE: when a question has multiple parts, be sure to look at other parts of the question - especially earlier ones! - as they may provide useful hints.
From the text: 1.20 a,b,d,h (find short strings!); 1.21 b; 1.29 b; 1.30.
Also: Use the pumping Lemma to show that the following languages over {a,b}are not regular:
i) the set of palindromes;
ii) the set of strings in which the number of a's is a perfect square.
Due in class: Oct 2.
From the text: 1.27; 1.28 a; 2.1 b,d; 2.9; 2.14 Bonus: 2.17
Due in class: Oct 11.
From the text: 2.2; 2.10; 2.17, 2.30 a,d; 2.44 Bonus: 2.35
Due in class: Oct 19.
From the text: 3.2 b,c; 3.4; 3.7; 3.8 b.
Due in class: Nov 2.
From the text: 4.2; 4.4; 4.6; 4.8; 4.10.
Due in class: Nov 13.
From the text: 4.12; 4.16; 5.1; 5.2
Due in class: Nov 23.
From the text: 5.3; 5.4; 5.17; 5.35
Due: Dec 1.