Quote:
Originally Posted by RupertPupkin
Hmm, I think you've got it, because it doesn't implicitly use an induction argument. That has to be the proof Davis and Weyuker had in mind. Good job! Finally, after all these years...I can't believe I never thought of that.  |
What's the induction proof? I came up with this (prior to seeing mtl2002's elegant one-liner):
ax = xb ( x := {a,b}* ) (0)
If x = <empty> then we get a = b which is a contradiction.
For non-empty x:
In order for ax = xb to hold, xb must start with an 'a', so x must start with an 'a'.
In order for ax = xb to hold, ax must end on a 'b', so x must end on a 'b'.
So x starts with an 'a' and ends on a 'b'. So x must have 2 different characters. (Corollary 0)
Given ax, xb and x, for the character in the i'th position ( i > 1 & i < |ax| ),
the following must hold:
ax[i] = xb[i] (1)
ax[i] = x[i-1] (2)
xb[i] = x[i] (3)
leading to:
x[i-1] = x[i] (4)
So for any x to satisfy (4), x must be empty or all the characters in x must be
the same, which contradicts Corollary 0. So there is no x for which (0) can be
satisfied.
mtl2002's 'proof' remains the most elegant.
David
..>
..>
Linear Mode
