418531 ภาคต้น 2552/โจทย์ปัญหาการพิสูจน์ II/เฉลยข้อ 8

ในการแก้ปัญหาข้อนี้เราจะให้ $\Sigma \,$ แทนเซตของพยัญชนะทั้งหมดที่เป็นไปได้ เช่น ถ้าสตริงที่เราสนใจเกิดจากการนำพยัญชนะของภาษาอังกฤษมาประกอบกัน เราอาจจะให้ $\Sigma =\{\mathrm {a,b,c,\ldots ,z} \}\,$ เป็นต้น

นอกจากนี้ เพื่อให้ไม่ให้เกิดความสับสน เราจะแทนสตริงด้วยตัวอักษรภาษาอังกฤษตัวเล็ก เช่น $x,y,z\,$ เป็นต้น และจะแทนตัวอักษรด้วยตัวอักษรกรีก เช่น $\alpha ,\beta ,\gamma \,$ เป็นต้น

ข้อย่อย 1

ให้ $x\,$ เป็นสตริง เรานิยามสตริงกลับ $x^{R}\,$ ของ $x\,$ ดังต่อไปนี้

$x^{R}={\begin{cases}\lambda ,&x=\lambda \\y^{R}\alpha ,&x=\alpha y\end{cases}}$

เมื่อ $y\,$ เป็นสตริงและ $\alpha \in \Sigma \,$ เป็นพยัญชนะ

ข้อย่อย 2

ให้ $P\,$ เป็นเซตของสตริงที่เป็นพาลินโดรม เราสามารถนิยาม $P\,$ ได้จากกฎต่อไปนี้

• $\lambda \in P$
• ถ้า $\alpha \in \Sigma$ แล้ว $\alpha \in P$
• ถ้า $\alpha \in \Sigma$ และ $x\in P$ แล้ว $\alpha x\alpha \in P$

ข้อย่อย 3

ในปัญหาข้อนี้ ให้ $n\,$ แทนความยาวของสตริง $x\,$ (ความยาวของสตริงคือจำนวนตัวอักษรในสตริงนั้น)

เราจะพิสูจน์ข้อความ $(xy)^{R}=y^{R}x^{R}$ โดยใช้ induction บนตัวแปร $n\,$

(Base Case) $n=0\,$ เราจะได้ว่า $x=\lambda \,$ ฉะนั้น $(xy)^{R}=(\lambda y)^{R}=y^{R}=y^{R}\lambda ^{R}=y^{R}x^{R}\,$

(Induction Case) ให้ $n\,$ เป็นจำนวนเต็มที่ไม่เป็นลบ และสมมติว่าสำหรับสตริง $z\,$ ที่มีความยาว $n\,$ ใดๆ $(zy)^{R}=y^{R}z^{R}\,$

ให้ $x\,$ เป็นสตริืงที่มีความ $n+1\,$ ใดๆ สมมติให้ $x=\alpha z\,$ โดย $\alpha \in \Sigma \,$

เราได้ว่า $(xy)^{R}=(\alpha zy)^{R}=(zy)^{R}\alpha =y^{R}z^{R}\alpha =y^{R}x^{R}\,$

ดังนั้นเราสามารถสรุปได้ว่า $(xy)^{R}=y^{R}x^{R}\,$ สำหรับสตริง $x\,$ และ $y\,$ ใดๆ