Which of the following are not regular ? (A) Strings of even number of a’s.…

Answer: The non-regular languages are strings of a’s whose length is a prime number, palindromes made up of a’s and b’s, and strings of a’s whose length is a perfect square.

• Even number of a’s (regular):

  This language is regular because it can be described by the regular expression (aa)*, or by a 2-state DFA that toggles parity on each a.

• Strings of a’s whose length is a prime number (non-regular):

  Proof sketch using the pumping lemma: Let p be the pumping length. Choose a prime N > p and take the string s = a^N in the language. Decompose s = xyz with |xy| ≤ p and |y| = k ≥ 1, so y = a^k. For i = N+1, the pumped string xy^{N+1}z has length N + k*N = N(1+k), which is composite (product of N and 1+k), so it is not prime-length. This contradicts the pumping lemma requirement that all pumped strings remain in the language. Hence the language is not regular.

• Palindromes over {a,b} (non-regular):

  Proof sketch using the pumping lemma: Let p be the pumping length and take s = a^p b a^p, which is a palindrome. Any decomposition s = xyz with |xy| ≤ p forces y to consist only of a’s from the left block. Pumping y (adding or removing a’s on the left side) breaks the symmetry between the two sides, so for some i the string xy^i z is not a palindrome. This contradicts the pumping lemma, so the palindrome language is not regular.

• Strings of a’s whose length is a perfect square (non-regular):

  Proof sketch using the pumping lemma: Let p be the pumping length. Choose a prime t > p and take s = a^{t^2}. Decompose s = xyz with |xy| ≤ p and |y| = k ≥ 1. Pump with i = t+1 to get length t^2 + k*t = t(t+k). If this were a perfect square, then t would divide that square, so t would divide its square root, implying the square root is t*u and t+k = t u^2. That gives k = t(u^2 -1). Since k ≤ p < t, the equality is impossible (u must be at least 1 and u=1 gives k=0 which is not allowed). Thus the pumped string is not a perfect square length, contradicting the pumping lemma; hence the language is not regular.

Therefore the only non-regular languages among the four given are: strings of a’s of prime length; palindromes over {a,b}; and strings of a’s whose length is a perfect square.