 #1
 29
 2
Homework Statement
Wherein α, β are strings, λ = ∅ = empty string, β^{r} is the shortest suffix of the string β, β^{l} is the longest prefix of the string β, and T* is the set of all strings in the Alphabet T, α denotes the length of a string α, and the operator ⋅ (dot) denotes concatenation of two strings.
Homework Equations
Proposition 1: ∀α ∈ T* (λ ⋅ α) = α
CONCATENATION, defined recursively:
CRC0: if β = 0, α⋅β = α ⋅ λ = α
CRC1: if β = 1, α⋅β : α + 1 → T such that
(α⋅β)(i) = α(i) if i < α
(α⋅β)(i) = β(0) if i = α
CRC2: if β > 1, α⋅β = (α ⋅ β^{l} ⋅ β^{r})
The Attempt at a Solution
I'm using induction on α (it seemed like it would be a bit easier this way when I started). I managed to prove the base case:
BASE CASE: Let α = 0. Then α = λ and
LHS = (α⋅β)^{r} = (λ⋅β)^{r} = β^{r} = RHS
The inductive step is proving much more difficult, though:
INDUCTIVE HYPOTHESIS: If α = n, then (α⋅β)^{r} = β^{r}
LHS = (α⋅β)^{r} = (α^{l} ⋅ (α^{r} ⋅ β))^{r} = (α^{r}⋅β)^{r} = (α^{r}⋅β^{l}⋅β^{r})^{r}
While I was applying my inductive hypothesis in the step
(α^{l}⋅(α^{r}⋅β))^{r} = (α^{r}⋅β)^{r} = (α^{r}⋅β^{l}⋅β^{r})^{r I noticed that if I could apply my inductive hypothesis again to the result: (αr⋅βl⋅βr)r This would leave me with the RHS, βr. However, in order to do that I'd have to be able to prove that the string (αr⋅βl) has length n. That's where I'm stuck. I can't think of a way to do that. I tried induction on β instead (just to see what would happen) and I ended up getting stuck in a similar way. Is there a way to prove that (αr⋅βl) = n? Or is there a better way to prove this that I'm not seeing? I don't know what else to try at this point. Note that I'm not limited to using only the equations/propositions specified in the homework template. Those are just some easy axioms that were proven in class. I can use any proposition/theorem as long as I show its proof.}
Attachments

14.9 KB Views: 430