Use the pumping lemma to show that the following languages are not regular.
a. A1 = {0n1n2n| n ≥ 0}
b. A2 = {www | w ∈ {a, b}∗}
c. A3 = {a2n| n ≥ 0} (Here, a2n means a string of 2n a’s.)
Indice dei contenuti
a. Theorem
A1 = {0n1n2n| n ≥ 0} is not regular.
a. Proof
Applying the pumping lemma to a string that matches with A1 we can have two scenarios:
- y is composed by only 0s or 1s or 2s. For example, 012 with y = 1. When we change the number of ys, we obtain a different number of 1s than others: 02, 0112, 01112, ..., and this doesn't match with A1 anymore
- y is composed by a pair or more of numbers. For example, 001122, with y = 0011. Changing the number of ys, the order of the numbers are not kept: 22, 0011001122, 00110011001122...
so A1 is not regular.
b. Theorem
A2 = {www | w ∈ {a, b}∗} is not regular.
b. Proof
We show that choosing a pattern w, composed by as and bs, the language A2, that recognizes the pattern w repeated three times, is not regular.
If the y part of the pumping lemma is composed by a substring of w, repeat the y more times means don't match A2 anymore, because the string can be composed by other than ws. I.E. w = aab, a valid string is aabaabaab, y = the central pair aa: repeating y, we obtain: aabbaab (0 times), aabaabaab (matches), aabaaaabaab (1 time). The first and the third examples are not composed by ws.
If the y part of the pumping lemma is exactly w, repeat the y a number of times different by 1 mod 3 (1, 4, 7, 10...) doesn't match the rule of three times w. I.E. w = aab, y = aab ⇒ aabaab (0 times, doesn't match); aabaabaab (1 time, matches), aabaabaabaab (2 times, doesn't match)...
So, A2 is not regular.
c. Theorem
A3 = {a2n| n ≥ 0} (Here, a2n means a string of 2n a’s.)
c. Proof
A3 recognizes a, aa, aaaa, aaaaaaaa, ...
Choose x = a, y = aa, z = a seems a good idea, because we're sure that every string recognized by A3 is writable with an xyiz, but there are two problems: a single "a" is not writable with this pattern, and there are strings that are writable but don't be recognized by A3, for example, i = 2 ⇒ a aa aa a (the spaces have been added to make the string more readable).
Choosing a simpler definition of x, y, z, as x = ε, y = a, z = ε, we are affected by the same problem.