Say I am given that means the string is spelled backwards. Ex:
= olleh
The definition is:
1. w is a string of length 0 then w^R = empty set
2. w = ua, where and , is a string of length n+1>0 then
prove the following:
a.
Use induction on the length of y. Condition 2. of the definition gives the base case, where y has length 1. If y has length n+1 then y=za, where z has length n. Use the inductive hypothesis to show that (you take it from there).
If you post a query at 5 a.m. (UK time), don't get ratty if I don't reply by 7 a.m.
Hello,
Yes, you guessed right. I gave you hints, it's up to you to make it into a rigorous proof. You should know what "a proof by induction" looks like: the base case and the inductive step (assuming that the assertion holds when the length is k-1 and prove it for k. As I wrote (x^R)^R=x, you see that I assumed that the length of x is k-1 and so on...)
Bye.
, is just the inductive hypothesis that you're assuming to help you solve the induction right?
you assume that a string x with a length of n holds the property , so therefore in your inductive proof that you show on your first post is the induction for n+1 and so on?
one last question, what would be the base case here? Is the base case for part a and b the same? From my point of view, we break w = ua. then assume that n = 0, and therefore u is a string of length 1 and so is a. So (au)^R is equal to au^R.
Please do correct me, as that's the way I see it
Hello,
It seems the base case is intended to be a string of length 0. (cf. Cond.1)
a. Prove (xy)^R=y^Rx^R where the length of y is 0.
Use y=y^R=empty set.
b. Prove (w^R)^R=w where the length of w is 0.
Use w=w^R=empty set.
The base case is not exactly "the same" since you prove something different. But you use the same fact (that is, Cond.1)...
Bye.