0
$\begingroup$

I'm just wondering about this question I've been working on for my review homework. I tried to solve it on my own and I feel my proof makes decent sense but not the best sense. Please try to give any hints or comments to help me with this thanks.

Question:

If w: {1,...,L} => {0,1} is a binary string, the complement of w, denoted w^c, is the string of length L defined by w^c(i) = 1 - w(i). The reverse of w, denoted w^R, is the string of length L defined by w^R(i) = w(L + 1 - i). Use these definitions to give a careful proof that, for every binary string x, (x^C)^R = (x^R)^C.

My Answer:

Proof By Induction:

Hypothesis:

We can see that x is a binary string with length L and has other strings such as x^C and x^R which are within the length 0 < i ≤ L where i is the position of a character in the string x.

Base Case:

x = {0,1}, L = 2, x^c(1) = 1, x^c(2) = 0, (x^c)^R(1) = 0, (x^c)^R(2) = 1 x^R(1) = 1, x^R(2) = 0, (x^R)^C(1) = 0, (x^R)^C(2) = 1 => (x^c)^R = {0,1}, (x^R)^C = {0,1} thus the base case holds.

Inductive Step:

Suppose for every binary string L = K the base case is satisfied for every character in the string x for 0 < i ≤ L. Then for L = K + 1 we have (x^c)^R(i) = x^c(k+2-i) ≡ 1 - x^R(i) which satisfies the base case because for every character at pos i it is equal because of outer bracket functions.

conclude:

Thus the assertion holds for L = K + 1.

I appreciate all sorts of criticism and help towards this question so I can gain the knowledge on what I am doing wrong.

Improve this question
$\endgroup$
0
$\begingroup$

To use induction, you should be clear that you are progressing from strings of length $L$ to strings of length $L+1$ by adding a new character at a specific location, either the beginning or the end. I will use the beginning. If $x$ is a new character and $s$ is a string of length $L$ where it is known (from the induction hypothesis) that $(s^C)^R=(s^R)^C$ you want to prove that $((xs)^R)^C=((xs)^C)^R$ To do so, you need to argue that $(xs)^R=sx$ and $(xs)^C=x^Cs^C$ and you will be home.

For the base case, you have $L=1$ and there are two strings of that length. You can just say $(0^R)^C=0^C=1=1^R=(0^C)^R$ and the same for $1$ and be done.

Improve this answer
$\endgroup$
  • $\begingroup$ Hi thanks for the information $\endgroup$ – geforce Sep 11 '14 at 21:35
  • $\begingroup$ I have a question about "L to strings of length L+1 by adding a new character at a specific location". How did you get the idea to add another character? Also is the L to L+1 part is for the inductive step? Shouldn't I use L=k instead? $\endgroup$ – geforce Sep 11 '14 at 21:39
  • $\begingroup$ Also why is the string labeled as S instead of X because the question says X is a binary string not character? Is the extra character added to compare the string with the char to show the position change after the reverse/complement function? Thanks $\endgroup$ – geforce Sep 11 '14 at 21:42
  • $\begingroup$ The idea of adding another character is in the spirit of an induction proof. You want to prove the assertion for $L+1$ from the known fact about $L$, so I want a string of length $L$ in my proof. Yes, I was sloppy about the use of $x$ and $s$-it would have been better to reverse them. $\endgroup$ – Ross Millikan Sep 12 '14 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.