To make things clear, I'll give the question as it was given to me. The explanation I've been given by my lecturer wasn't clear to me, and Google has not helped thus far.
Considering the following inductive specification of strings:
S ::= ε | aS
Where symbol 'a' stands for any character not equal to ε.
We can inductively define the function length(s) with s ∈ S, that
returns the length of a given string:
length(ε) = 0
length(aS) = 1 + length(S)
Now, we define inductively "string concatenation". That is, for all
s1, s2 ∈ S the concatenation of s1 and s2, written s1 + s2, is defined
as:
s1 = ε : ε + s2 = s2
s1 = as'1: as'1 + s2 = a(s'1 + s2)
Show that:
1. if s ∈ S, then s + ε = s
2. if s1, s2 ∈ S, then it holds that
length (s1 + s2) = length(s1) + length(s2)
What I can't understand, is (where I failed) how to answer either of those questions without simply repeating what was given inductively above.
I'm not necessarily seeking the answer, just an understanding on how to even go about this.