a. Definition: The reverse of a string u, denoted uR, is defined recursively as

Question

a. Definition: The reverse of a string u, denoted uR, is defined recursively as follows: (1) = (Note that is the empty string.) (2) For any character a, and any string w, then (wa)R -awR This definition, in words, is on page 14. Claim: (uv)R-vRuR for any strings u and v Proof. By structural induction on v. Base case: E. Let u be any string (ue)R- Induction step: Let v be an arbitrary string. Assume that for all strings u, (uv)-vRuR. We need to show that, for each character a and all strings u, (u v)(va)RuR By the recursive definition of reverse: (u va)R By the inductive hypothesis: (uv)R Also, by the recursive definition of reverse: (va)R Thus, (u va)R def (IH) (def) (va)RuR

Explanation / Answer

1.
(u)R = (u) R = uR = RuR

2.
By recursive definition (u va)R = (va)R (u) R
By inductive hypothesis (uv)R = vRu R

Also by recursive definition of reverse: (va)R = avR

3.
(u va)R (def) = avRu R = (va)Ru R

            (IH) = (va)R (u) R

1.
(u)R = (u) R = uR = RuR

2.
By recursive definition (u va)R = (va)R (u) R
By inductive hypothesis (uv)R = vRu R

Also by recursive definition of reverse: (va)R = avR

3.
(u va)R (def) = avRu R = (va)Ru R

            (IH) = (va)R (u) R

I hope this now makes sense!!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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