Question

Which of the following are not regular?

(a) String of )’s which has length that is a perfect square

(b) Palindromes Consisting of 0’s 1’s

(c) String of 0’s whose length is a prime number

(d) All of the mentioned

I had been asked this question in a job interview.

Query is from Finite Automata and Regular Expressions in division Compiler Introduction of Compiler

Answer 1

Correct option is (d) All of the mentioned

Easy explanation: Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.