Let A be the set of palindromes over {a, b}. Suppose you are trying to prove tha

Question

Let A be the set of palindromes over {a, b}. Suppose you are trying to prove that A is not regular using the pumping lemma. Your proof starts (correctly) like this: Suppose for a contradiction that A is regular. Let p be the pumping length given by the pumping lemma. Now you have to choose string s. For each choice of s below, you have to state whether or not this choice of s can be used to finish the proof that A is not regular. If you answer that s can not be used, you should also briefly and clearly explain why it can not be used. If you answer that s can be used, you do not have explain anything. (a) s = b^p a^p b^p. Can this s be used? yes/no. If you said no. briefly explain your answer. (b) s = a^p. Can this s be used? yes/no. If you said no. briefly explain your answer. (c) s = a^p b^p. Can this s be used? yes/no. If you said no. briefly explain your answer. (d) s = a^p-1 ba^p-1. Can this s be used? yes/no. If you said no. briefly explain your answer. (e) s = aaabbaaa. Can this s be used? yes/no. If you said no. briefly explain your answer. (f) s = (ab)^p a. Can this s be used? yes/no. If you said no. briefly explain your answer. (g) s = a^p ba^p. Can this s be used? yes/110. If you said no. briefly explain your answer.

Explanation / Answer

(a) yes

(b) no. Because even after splitting the string, it will always be x(y^i)z will always be a^(something) which is a palindrome.

(c) yes

(d) No. While splitting the string to x,y,z. if y = b, then
x(y^i)z is a palindrome always.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.