Question

Which of the following is not an application of Pumping Lemma?

(a) {0^i1^i|i>=0}

(b) {0^ix|i>=0, x∈{0, 1}* and |x|<=i}

(c) {0^n| n is prime}

(d) None of the mentioned

This question was addressed to me during an interview.

Question is from Applications of Pumping Lemma/Pigeonhole principle topic in chapter Properties of Regular Languages of Automata Theory

Answer 1

Right option is (d) None of the mentioned

To elaborate: None of the mentioned are regular language and are an application to the technique Pumping Lemma. Each one of the mentioned can be proved non regular using the steps in Pumping lemma.