🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Pumping Lemma and Minimisation: all 10 questions

Quiz: Pumping Lemma and Minimisation · Question 9 of 10

What does this print? (code)

What does this print?

p = 4
s = "a" * p + "b" * p
splits = [(i, j) for i in range(p + 1) for j in range(i + 1, p + 1)]
in_L = lambda w: w == "a" * (len(w) // 2) + "b" * (len(w) // 2)
print(len(splits), all(not in_L(s[:i] + s[i:j] * 2 + s[j:]) for i, j in splits))
  1. A.4 True
  2. B.10 False
  3. C.10 True
  4. D.16 True
Answer & explanation

Correct answer: 10 True

There are 10 splits with |xy| ≤ 4 and |y| ≥ 1, and pumping up (i = 2) breaks every one of them.

Can you get the rest right without peeking?

Take the timed Quiz: Pumping Lemma and Minimisation quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →