Question

Which of the following are non regular?

(a) The set of strings in {a,b}* with an even number of b’s

(b) The set of strings in {a, b, c}* where there is no c anywhere to the left of a

(c) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3. Interpret the empty strings e as the number 0.

(d) None of the mentioned

I have been asked this question at a job interview.

This intriguing question comes from Properties-Non Regular Languages in chapter Regular Expressions and Languages of Automata Theory

Answer 1

Correct choice is (d) None of the mentioned

To explain: All of the given languages are regular and finite and thus, can be represented using respective deterministic finite automata. We can also use mealy or moore machine to represent remainders for option c.