There is one big piece, that reads:
Here is my proof for your request. To prove that L = {a
n
b
ma
2(m+n)
| m, n =1}, over
alphabet S = {a, b}, is not regular, I will appeal to the well-known Pumping Lemma
.
Here are the other pieces they’ve transcribed:
(a) Now consider w = abaaaa.
(b) Now consider w = a
k
b
ka
4k
.
(c) Thus, w = xyz such that |xy| = k and |y| = 1.
(d) Then, it follows that w ? L (where m = n = 1) and |w| = 6 = 1.
(e) Then, it follows that w ? L (where m = n = k) and |w| = 6k = k.
(f) Consider now i = 1. Then, xyi
z = xyz = a
qa
ra
s
b
ka
4k = a
q+r+s
b
ka
4k
.
(g) Consider now i = 0. Then, xyi
z = xy0
z = xz = a
qa
s
b
ka
4k = a
q+s
b
ka
4k
.
(h) So, it follows that x = a, y = b, and z = aaaa. Clearly w = abaaaa = xyz.
(i) Assume that L is regular. Then, there exists a k ? N as per the Pumping Lemma.
(j) Consider now i = 2. Then, xyi
z = xyyz = abbaaaa. It is then clear that xyi
z 6? L.
(k) Now, because q + r + s = k and r = 1, we know that q + s 6= k, and therefore, xyi
z 6? L.
(l) Thus we have a contradiction: our assumption (that L is regular) must be true and L is true.
(m) Now, because q + r + s = k and r = 1, we know that a
qa
ra
s = a
k
, and therefore, xyi
z ? L.
(n) So, there exist substrings x, y, z ? S
*
satisfying the four Pumping Lemma conditions.
(o) Thus we have a contradiction: our assumption (that L is regular) must be false and L is not regular.
(p) So, it follows that x = a
q
, y = a
r
, z = a
s
b
ka
4k
, where q + r = k, r = 1, s = 0, and q + r + s = k.
You need not write out the entire proof, just provide the corresponding letters in the correct order as
a word in the submission form. For example, the word badf denotes the proof built from statements
(b), (a), (d), and (f) in that exact order. And remember: the burglars wrote down multiple different
interpretations of the same piece of the proof, so not all of these will be necessary or correct. However,
all necessary pieces are listed. Your answer should be entered in the assignment submission form.
(d) (10 marks) Let L = {a
2k
cbk
| k = 0}. Prove that there is no DFA for L by completing the following
proof. Concretely, you need to fill each of the seven missing parts.
1. Assume that there is a DFA M which accepts L and hence that .
2. Then, by the Pumping Lemma from Exercise 3.(a) above applies for some n = 1.
3. Then, consider string w = .
4. Clearly, w ? L and |w| > n.
5. So, by the Pumping Lemma, .
6. Because |xy| = n, it must be the case that .
7. Now consider the word w
0 = .
8. By the Pumping Lemma, it follows that w
0 ? L.
9. However, .
(c) (10 marks) Emma’s Pumping Lemma Dilemma:
Exercise 3: Pumping Lemma & Regularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 marks
10. So we reach a contradiction, and L cannot be regular.
11. Finally, due to the we know that a language is regular if and only if it can be recognised
by a DFA. Therefore, since L is not regular, there is no DFA that recgonises language L.
(e) (4 marks) Let L2 = {a, b}
* \ {a
n
b
ma
2(m+n)
| m, n = 1} be a language over S = {a, b}. Prove that
there is no DFA M such that L(M) = L2. Your proof should be short and not use the Pumping Lemma.
(a) Complete the four missing requirements (i)-(iv) in the following statement:
Pumping Lemma: Let L be a regular language. Then, there exists an integer n = 1 such that for every
w ? L with |w| = n, there exist strings x, y, z ? S*
, such that:
i. (1 mark)
ii. (1 mark)
iii. (1 mark)
iv. (1 mark)
