CSU390 03F Honors Adjunct Information

Points	Grade
90+	A
80-89	A-
70-79	B+
60-69	B
50-59	B-
40-49	C+

Note that your grade is based on the total number of points you earn. For example, one could achieve an "A" by attempting 90 points worth of problems and solving them perfectly, or by attempting 180 points worth of problems and obtaining 1/2 credit on each, etc.

Your solutions and/or programs will be due no later than the date of the scheduled final exam for this course, Fri Dec 19.

Finite Automata, Regular Expressions, and the Regular Languages

1. [40 pts] Simulation and manipulation of DFAs.

   • Devise an encoding for DFAs that can be easily parsed by a computer program. The encoding can be of your choice, but you must effectively incorporate all of the information in the standard 5-tuple for DFAs. For example, the following is a reasonable (and easily parsable) representation of the DFA M1 given in Exercise 1.1 of the Sipser text:

     3
     q1 q2 q3
     2
     a b
     q2 q1
     q3 q3
     q2 q1
     q1
     1
     q2
     

     Line 1 specifies the number of states, and Line 2 specifies states. Line 3 specifies the size of the alphabet, and Line 4 specifies the alphabet. Lines 5-7 give the transition function, each row corresponding to a state (in order) and each column corresponding to a symbol from the alphabet (in order). Line 8 specifies the start state. Line 9 specifies the number of final states, and Line 10 specifies the final states.

     You need not use this encoding, but you must specify (and use) some consistent encoding.

   • Write a procedure for simulating DFAs; i.e., given as input an encoding for a DFA and a string, your simulator should properly return "accept" or "reject."

   • Write a procedure which constructs the complement of a DFA; i.e., given as input an encoding for a DFA, your program should return an encoding of the complement of that DFA.

   • Write a procedure which constructs the intersection of two DFAs; i.e., given as input the encodings of two DFAs, your program should return an encoding of the DFA which corresponds to their intersection. Use the Cartesian product construction described in the proof of Theorem 1.12 and Footnote 3 on page 46.

   • Write a procedure which constructs the symmetric difference of two DFAs (see page 155 for the definition of symmetric difference). Such a program is simple given procedures for constructing complement and intersection.

   • Write a procedure for determining if the language accepted by a given DFA is empty. See the proof of Theorem 4.4 for the basic idea.

   • Write a procedure for determining if the languages accepted by two DFAs are equivalent. See the proof of Theorem 4.5 for the basic idea.

   You must submit your program code and provide a demo.

2. [5 pts] Consider the following language: NotPrime = {1ⁿ : n is not a prime}. Show that NotPrime is non-regular by using the Pumping Lemma. (One could prove that NotPrime is non-regular by showing that Prime is non-regular and using the fact that the class of regular languages is closed under complement; however, in this problem you should show that NotPrime is non-regular directly by using the Pumping Lemma.)

   Hint: You may assume the following mathematical fact (Dirichlet's Theorem). First, however, we'll need a bit of background.

   Two integers a and b are said to be relatively prime if they share no factors in common. For example, 15 and 26 are relatively prime since the prime factors of 15 are {3, 5} and the prime factors of 26 are {2, 13}; however, 15 and 25 are not relatively prime since they share the factor 5 in common.

   Given two numbers a and b, the arithmetic progression a + bn is the sequence of numbers corresponding to the above formula for n = 1, 2, 3, and so on. For example, 3 + 10n = (13, 23, 33, ...).

   Dirichlet's Theorem

   If a and b be relatively prime positive integers, then the arithmetic progression a + bn contains infinitely many primes.

3. [5 pts] Consider the following language: Even₃ = {w : w in {0,1,2}^* and w is an even integer in base 3}. You should either
   • prove that Even₃ is non-regular, or
   • show that it is regular by constructing a finite automata which accepts it.

   Hint: You may wish to make use of the following facts: The sum of an odd number of odd integers is odd, and the sum of an even number of odd integers is even. (If you use these facts, you should prove them as part of your solution.)

4. [5 pts] Prove that the regular languages are closed under the following operation.
   HalfPal(A) = {w | ww^R in A}

5. [10 pts] Prove that the regular languages are closed under the following operation.
   FirstThird(A) = {x | xyz in A, |x| = |y| = |z|}

6. [10 pts] Prove that the regular languages are closed under the following operation.
   LastThird(A) = {z | xyz in A, |x| = |y| = |z|}

7. [15 pts] Prove that the regular languages are closed under the following operation.
   MiddleThird(A) = {y | xyz in A, |x| = |y| = |z|}

Pushdown Automata, Context-free Grammars, and the Context-free Languages

1. [5 pts] Exercise 2.6 (d)

2. [5 pts] Exercise 2.18 (d)

3. [10 pts] Exercise 2.21 (b)

4. [10 pts] Exercise 2.26

Turing Machines, Decidability, NP-Completeness

1. [30 pts] Turing Machine simulator.
   • Devise a encoding for Turing Machines that can easily be parsed by a computer program. See the similar problem for DFAs described above for an example of what this encoding might look like.

   • Write a procedure for simulating Turing Machines; i.e., given as input an encoding for a Turing Machine and a string, your simulator should properly return "accept" or "reject."

   You must submit your program code and provide a demo on a "reasonable" Turing Machine, such as the one given in Figure 3.4.

2. [5 pts] Exercise 5.15

3. [10 pts] Exercise 5.19

4. [15 pts] Exercise 5.22

   Hint: Reduce from A_TM. Assume, without loss of generality, that a Turing machine which accepts the empty language does not have property P. (If not, consider the complement of property P. If the complement of property P is undecidable, then so is P since the decidable and undecidable languages are closed under complement.)

   Given an instance <M,w> of A_TM, your task is to construct a TM M' so that M' has property P if and only if M accepts w.

5. [10 pts] Exercise 5.23. Consider the two conditions (a) and (b) as stated in Exercise 5.22. Show that there exists a decidable language which satisfies condition (a) but not (b), and show that there exists a decidable language which satisfies (b) but not (a). Thus, both conditions (a) and (b) are necessary for Rice's Theorem.

6. [5 pts] Exercise 7.29. If P = NP, then a polynomial time algorithm for SAT exists. Use this algorithm as a subroutine to learn the truth settings for the variable of phi. (You will make multiple calls to the subroutine, each time learning the truth setting for one variable.)

7. [10 pts] Exercise 7.30. If P = NP, then a polynomial time algorithm for CLIQUE exists. Use this algorithm to help you solve this problem. There are essentially two parts: (1) determining the size of the max clique and (2) determining the vertices in the max clique.