Exercises

Exercise 1.  Assigned Wednesday, September 8; due Tuesday, September 14 in class.

Consider the following lemma.

Lemma 1.  Let L be a regular language.  Then there is a constant P depending only on L such that for any string t in L, and for every way of factoring t as t = uvw, such that |v| = P, there is a way to further factor v as v = xyz such that |y| > 0 and uxyizw is also in L for every i >= 0.

a.  Discuss what this lemma means.

b.  Discuss how this lemma differs from the pumping lemma presented in class.

c.  Prove the lemma.

Exercise 2.  Assigned Thursday, September 16; due Tuesday, September  21 in class.

Consider the following grammar that generates strings over the symbols 0 and 1.

S --> 0 S 0

S --> 1 S 1

S --> 0

S --> 1

S --> empty string

Prove by induction all of the strings in L(G) are palindromes.

Exercise 3.  Assigned Thursday, September 23; due Thursday, September 30 in class.

Do exercises 5.1, 5.4, 5.6, 5.10, and 5.13

Exercise 4.  Assigned Friday, October 1; due Thursday, October 7

1.  Write, compile, and run a self replicating program in the spirit of SELF in section 6.1 of the book.

2.  Do exercise 6.3

3.  Do exercises 7.1 and 7.2

Exercise 5.  Assigned Thursday, November 18; due Tuesday, November 23. 

1.  Do problems 7.16 and 7.22 in the book.

2.  You are going to be turning in a "term paper."  Unlike other term papers, this is to be a paper that discusses the theory of computing in terms that you would use to reach a computer science sophomore who has become familiar with programming, data structures, and algorithms, but who has not yet had a course on the theory of computing.  The paper is not intended to teach the theory of computing to such students, but rather to give them an intuitive grasp of

bulletwhat the theory of computing is about
bullethow it affects the practice of programming
bulletwhy it is important

The paper is to start with the concept of computability (i.e., not with finite state automata) and end with tractability and intractability.  We will discuss this some on Tuesday, November 23, although the paper will not be due then.

The most important thing to remember is your audience.  I am not the audience.  The audience is computer science sophomores.

 

Exercise 6.  Assigned Thursday, December 2, Due Tuesday, December 7.

Do exercise 7.22 again.  This time add the following.

  1. Describe the issue that we discussed in class regarding this problem (why most of the submitted solutions I was looking at were incorrect).  The purpose of this particular part of the assignment is to ensure that you recognize the problem and that you know what you need to do to solve it.
  2. Use part a of 7.22 to resolve the issue.

Your proof in part b should very clearly show that the reduction works.  That is, you must show that if x is in 3SAT then f(x) is in \=SAT and that if f(x) is in \=SAT then x is in 3SAT.