1. [10 points (a) [6 points] Let the alphabet -{a, b). A string z E , is called

Question

1. [10 points (a) [6 points] Let the alphabet -{a, b). A string z E , is called a palindronne if z-rr (r reads the same backward as forward); for example, the string abaaaba is a palindrome. Consider the following binary relation R on ": For all z, y E . z Ry if and only if 11-lyl and ryr is a palindrome. Note: ry is ), not (ry) i. [5 points] Show that R is an equivalence relation on ii 1 point] For an arbitrary z e ., describe the equivalence class [r] R (the equivalence class of R containing r). Justify your answer

Explanation / Answer

1)

i) xRx : same strings are related to each other by definition.

ii) if xRy then yRx : size(x) = size(y) and xyr

is a palindrome. reverse of a palindrome is also a palindrome. hence yxr

is also a palindrome. Hence yRx.

iii) if xRy and yRz then xRz : size(x) = size(y) = size(z). xyr and yzr  

are palindrome. x is same as y since xyr is palindrome and similarly y is same as z. hence x and z are same. hence xzr

is also a palindrome.

hence xRz.

Hence R is equivalence relation.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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