Which of the following languages are regular? Justify each answer. Pertaining to automata.?

Question

(a) L1 = {wcw | w contained in {a, b}*}
(b) L2 = {xy | x, y contained in {a, b}* and |x| = |y|}
(c) L3 = {an | n is a prime number}
(d) L4 = {(a^m)(b^n) | gcd(m, n) = 17}.

I need to prove whether these are regular languages or not using Myhil Nerode or the pumping Lemma. Can anyone help??!!

Answer 1

In general any lanuages with words of unbounded length ,where the same pattern is repeated in form or length, usually are not regular.

I'm sorry I'm not familiar with Myhil Nerode, so if an answer depends upon that, I can't help you.

L1 is not regular. Proven via the Pumping Lemma.

Since wcw is unbounded, if it were a regular expression, it would need to accept regular expressions of the form uv*w. NOTE: The w here is not the same as the w in wcw. I used uv*w, because that's the tradition in the Pumping Lemma. Let me replace uv*w with UV*W to keep the two straight.

Since wcw needs to accept UV*W, where can the "c" reside in UV*W?

Can it be in U? No, because then the V would pump a bunch of a's and b's to place accept string with more characters on the right of w than the left.

Can w be in V? No, because pumping the w within V would accept more than on w (or none.)

Can w be in W? No for the same reason it can't be in U.

L2 is regular. It's just another way of stating that you have an even number of a's and b's. The don't have to be the same, and I don't think you need to know where the xy split is. You could "implement" an FA with 2 states. One state is the start state, and the other is the final state. The transitions for a and b just hop back and forth between the two. I think that's all you need to show.

L3 is not regular using the pumping lemma.

Since a^n (where n is prime) is unbounded, it needs to accept a set of a's in the form of uv*w. Consider what happens you when pump v the following number of times |u| + |w|.

You'll get a string of a's of the following length:

|u| + |v| * (|u| + |w|) + |w|

The first |u| comes from the u. The last |w| comes from the w. The middle |u| + |w| comes from the pump of v which is of length |v|. To make it easier, let's use capital letters for length.

Therefore the length of the string accepted is:

U + V(U+W) + W

U + V*U + V*W + W

U(1 + V) + W(1 + V)

(U + W) * (1 + V)

Aha. The length of the string is a produce of two integers. Therefore it is not prime. We've pumped uv*w to a string that can't be prime.

L4 - No idea. I suspect this may be where Myhil Nerode comes in.

Answer 2

a and b are regular. They satisfy pumping lemma.