Reference no: EM131577756

Question: Show that the set {0²ⁿ1ⁿ | n = 0, 1, 2,...} is not regular using the pumping lemma given in Exercise.

Exercise: One important technique used to prove that certain sets are not regular is the pumping lemma. The pumping lemma states that if M = (S, I, , s0,F)is a deterministic finitestate automaton and if x is a string in L(M), the language recognized by M, with l(x) ≥ |S|, then there are strings u, v, and w in I ∗ such that x = uvw, l(uv) ≤ |S| and l(v) ≥ 1, and uvi w ∈ L(M) for i = 0, 1, 2,.... Prove the pumping lemma.