1
$\begingroup$

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.

  • 0
    Removed second part, wasn't as necessary.2011-10-04

1 Answers 1

3

I’ll do (1) as an illustration. Concatenation is defined by two clauses:

$\qquad(1)$:$\qquad\epsilon+s_2=s_2$
$\qquad(2)$:$\qquad as_1'+s_2=a(s_1'+s_2)$

What you need here is what is sometimes called structural induction: you prove that the base cases $-$ those given by clause $(1)$ $-$ satisfy the desired condition, and then you show that the condition is preserved by the inductive part of the definition (clause $(2)$).

Suppose that $s\in S$. Since $S::=\epsilon\mid aS$, either $s=\epsilon$, or s=as' for some s'\in S. If $s=\epsilon$, then $s+\epsilon=\epsilon+\epsilon$, and clause $(1)$ (with $\epsilon$ substituted for $s_2$) says that $\epsilon+\epsilon=\epsilon$, so $s+\epsilon=\epsilon=s$.

Now suppose that s=as' for some s'\in S such that s'+\epsilon=s'. Then \begin{align*} s+\epsilon&=as'+\epsilon\\ &=a(s'+\epsilon)\tag{by (2)}\\ &=as'\tag{induction hypothesis}\\ &=s. \end{align*}

It follows that $s+\epsilon=s$ for all $s\in S$.