- #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:

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})

^{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.}