Question

a) Give a recursive definition of the length of a string.

b) Use the recursive definition from part (a) and structural induction to prove that\(l\left( {xy} \right) = l\left( x \right) + l\left( y \right)\).

Short answer

a) Length of the string is\(l\left( {{b_1},{b_2},{b_3},\_\_\_\_{b_{n - 1}}} \right) = l\left( {{b_1},{b_2},{b_3},\_\_\_\_{b_{n - 1}}} \right) + 1\).

b) Thus, prove\(l\left( {xy} \right) = l\left( x \right) + l\left( y \right)\).

Step-by-step solution

Recursively Defined Functions.

We use two steps to define a function with the set of non-negative integers as the domain.

Basis step:-Enter a function value of zero.

Recursive step:-Give a rule for finding its value on an integer from its value on smaller integers.

Structural induction.

Structural induction is used to show that some statement P(x) holds for all x of some recursively defined structure such as formulas, lists, or trees.

Step 3:a) Give a recursive definition of the length of a string.

1) Solution.

Let the empty string \(\lambda \) has length\(0\).

\(l\left( \lambda \right) = 0\)

\({b_1},{b_2},{b_3},\_\_\_\_{b_{n - 1}}{b_n},\)

Then its length is one greater than the length of the string, \({b_1},{b_2},{b_3},\_\_\_\_{b_{n - 1}}\).

\(l\left( {{b_1},{b_2},{b_3},\_\_\_\_{b_{n - 1}}} \right) = l\left( {{b_1},{b_2},{b_3},\_\_\_\_{b_{n - 1}}} \right) + 1\).

prove that\(l\left( {xy} \right) = l\left( x \right) + l\left( y \right)\).

1) Explanation.

In the given question,

\(l\left( {xy} \right) = l\left( x \right) + l\left( y \right)\).

2)Basic step.

Let,

\(\begin{array}{c}\lambda = 0\\l\left( {\lambda \lambda } \right) = l\left( \lambda \right)\\ = 0\\ = l\left( \lambda \right) + l\left( \lambda \right)\end{array}\)

The statement holds for the basic step.

3) Recursive Step

Let\(l\left( x \right) = n{\rm{ and }}l\left( y \right) = m\).

Here let,

\(\begin{array}{c}x = {x_1}{x_2} - - - {x_n}\\y = {y_1}{y_2} - - - {y_m}\end{array}\)

4) Solution.

Here prove\(l\left( {xy} \right) = l\left( x \right) + l\left( y \right)\).

\(\begin{array}{c}l\left( {xy} \right) = l\left( {{x_1}{x_2} - - - {x_n}{y_1}{y_2} - - - {y_m}} \right)\\ = l\left( {{x_1}{x_2} - - - {x_n}{y_1}{y_2} - - - {y_{m - 1}}} \right) + 1\\ = l\left( {{x_1}{x_2} - - - {x_n}{y_1}{y_2} - - - {y_{m - 2}}} \right) + 2\\ \vdots \\ = l\left( {{x_1}{x_2} - - - {x_n}} \right) + m\\ = l\left( x \right) + m\\ = l\left( x \right) + l\left( y \right)\end{array}\)