Question 1.

a) The following list includes different pieces of a proof that proves L = {waw_R | w is any string over {a, b}}, over alphabet = {a, b}, is not a regular language.

Some of these pieces are incorrect, not all pieces should be used in the final proof. However, all correct pieces are included in the list.

The first, correct, piece starts with:

Here is my proof for your request during your interview. To prove that L = {waw_R | w is any string over {a, b}}, over alphabet = {a, b}, is not regular, I will appeal to the well-known Pumping Lemma.

Here are the other potential pieces:

Please give the right combination of pieces that will result in the correct proof.

b)

Let L₂ = {b^kac^2k | k 0}. Prove that there is no DFA for L₂ by completing the following proof.

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 2 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' = _______

8. By the Pumping Lemma, it follows that w' L₂ .

9. However, _______.

10. So we reach a contradiction, and L 2 cannot be regular.

11. Finally, due to _________ 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₂ .

(a) | Thus, w xyz such that lxy| k (d) | Consider now i-2. Then, xyz--abkababka, or ryyz-abk bi abka. (e) Now consider w- abbbabbba (f)Assume that L is regular. Then, there exists ak E N as per the Pumping Lemma (g) Thus we have a contradiction: our assumption (that L is regular) must be true and L is true (h) | Consider now i 2. Then, xy'z-xyyz = abbbbbbabbba. It is then clear that xy'z L (i) | So, it follows that x = a, y = bbb, and abbba. Clearly w = abbba bbba-xyz (G) Thus we have a contradiction: our assumption (that L is regular) must be false and L is not regular (k) | Then, it follows that w L and |w| = 9 (I) So, it follows that y is of the form ab for some1j k (d) | Consider now i-2. Then, xyz--abkababka, or ryyz-abk bi abka. (e) Now consider w- abbbabbba (f)Assume that L is regular. Then, there exists ak E N as per the Pumping Lemma (g) Thus we have a contradiction: our assumption (that L is regular) must be true and L is true (h) | Consider now i 2. Then, xy'z-xyyz = abbbbbbabbba. It is then clear that xy'z L (i) | So, it follows that x = a, y = bbb, and abbba. Clearly w = abbba bbba-xyz (G) Thus we have a contradiction: our assumption (that L is regular) must be false and L is not regular (k) | Then, it follows that w L and |w| = 9 (I) So, it follows that y is of the form ab for some1j