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.