Use the Myhill-Nerode theorem (instead of the pumping theorem, which we will study later) to show that the language ? = {a}, L= {a^p : p is a positive prime integer } is not regular. In particular, show that for any pair of different positive prime integers p and q with p strings a^p and a^q are in different equivalence classes of ?L.

No fancy number theory is needed for this problem. You only need to know and use the definitions of "prime" and "composite".

Reminder: 1 is not a prime integer. The first few positive prime integers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.

Your proof should not mention the word "state"; it should directly use the definition of ?L.

Hints: Let k = q - p. Here are a couple of possible approaches. (You may come up with something different):

Approach 1. Assume that there is such a pair of primes p and q that are in the same equivalence class; show that this leads to a contradiction. A start: If q and p are in the same equivalence class, what can you say about p + k?

Approach 2: Of course if there is a distinguishing string for ap and aq, it will be at for some t. Your job is to find a non-negative integer t such that concatenating at onto ap and aq produces one string of prime length and one whose length is composite. Obviously, this value of t will depend on p and q. So you must show (as a formula or algorithm) how to find the t for each p and q, and convince me that it is correct. This is not trivial. Hint for the hint: For any n and m, we can find n consecutive composite numbers that are at least as large as n. Finding the distinguishing t for a few particular p-q pairs may help you discover the general pattern, but you will not receive much credit for only doing some specific cases.