CSG714 04S: Homework 02

Assigned: Thu 22 Jan 2004
Due: Wed 28 Jan 2004

General Instructions

1. Please review the grading policy outlined in the course information page.

2. On the first page of each part of your solution write-up, you must make explicit which problems are to be graded for "regular credit", which problems are to be graded for "extra credit", and which problems you did not attempt. Please use a table something like the following

   Problem	01	02	03	04	05	06	07	08	09	...
   Credit	RC	RC	RC	EC	RC	RC	NA	RC	RC	...

   where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.

3. You must also write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.

Specific Instructions

I will make available a handout on the Myhill-Nerode Theorem and minimization of finite automata. You may obtain this handout from a box outside my office.

Problems

Required: Problem 0 and six of the problems numbered 1 to 9
Points: 18 pts per problem (not including Problem 0)

0. Please send me the following information, via e-mail:
   • Your name.
   • Your preferred e-mail address.
   • Your affiliation and degree program (e.g., "College of Computer and Information Science, Ph.D. candidate).

   I will use this information to create an e-mail list in order to disseminate information, hints and corrections, etc.

1. Exercise 1.17, using the Pumping Lemma.

2. Exercise 1.17, using the Myhill-Nerode Theorem.

3. Exercise 1.23, parts (a,c,d). Hint: Use of closure properties may help.

4. Exercise 1.37. Furthermore, prove that the language in question is, in fact, non-regular.

5. Using the algorithm discussed in class, minimize the following DFA:
   

6. 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.

7. Show that the following language is non-regular.
   • {0ⁱ1^j | i and j are relatively prime}

8. Prove that the regular languages are closed under the following operations:
   • FirstThird(A) = {x | xyz in A, |x| = |y| = |z|}
   • LastThird(A) = {z | xyz in A, |x| = |y| = |z|}

9. Prove that the regular languages are closed under the following operation:
   • MiddleThird(A) = {y | xyz in A, |x| = |y| = |z|}

Switch to:

• Homework 01
• Homework 03