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.
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:
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
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.
14.9 KB Views: 430