Proof by Induction of shortest suffix of concatenated string

[Enharmonics]

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:

C-RC0: if |β| = 0, α⋅β = α ⋅ λ = α

C-RC1: if |β| = 1, α⋅β : |α| + 1 → T such that
(α⋅β)(i) = α(i) if i < |α|
(α⋅β)(i) = β(0) if i = |α|

C-RC2: 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)<sup>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.</sup>

 

[tnich]

It seems to me that given $(\alpha_n \cdot \beta)^r = \beta^r$, you need to show that $(\alpha_{n+1} \cdot \beta)^r = \beta^r$. How would you construct $\alpha_{n+1}$ given $\alpha_n$?