Which of the following are not regular? (A) Strings of even number of a's
Which of the following are not regular?
(A) Strings of even number of a's
(B) Strings of a's, whose length is a prime number
(C) Set of all palindromes made up of a's and b's
(D) Strings of a's whose length is a perfect square
Show answerHide answer
Correct answer: (C) (B), (C) and (D) only
Explanation
(A) Strings with an even number of a's is regular, since a finite automaton can accept it. (B) Strings of a's whose length is prime, (C) palindromes over {a, b} and (D) strings of a's whose length is a perfect square are not regular: no finite automaton can accept them (provable with the pumping lemma).