Solu tion
For all a ∈ ′
Σ and w any string on Σ, we make a recursive definition as
| | , | | | |
a
wa
w
=
=
+
1
1
With this formal definition, we can prove
| | | | | |
uv
u v
= + .
By this definition made, | | | | | |
uv
u v
= + holds for all u of any length and v of
length 1, which is the basis.
Let us assume v of length n + 1 and we write it as
v = wa.
Therefore we have, | | | | ,
v
w
=
+1
| | |
| | |
uv
uwa
uw
=
=
+1
But by inductive hypothesis,
| | | | | |
uw u w
= +
so that
| | | | | |
| | | |
uv
u w
u v
=
+ + = +
1
Hence for all u and all v of length upto n +1, we have
| | | | | |
uv u v
= +
which is the inductive step.
Ì Exam ple 0.1.20: Use induction on to show that | |
| |
u
n u
n
=
for all
strings u and all n.
Solu tion
Basis: For n = 1, |u
1 | = |u| = l (assume)
n u
u u
| | | | | |
=
= =
1
1
Inductive Hypothesis: Let us assume that it is true for n.
| | | |.
u
n u
n
=
Induc tive Step:
|
| |
| | | | |
| | | |
(
) | |
u
u u
u
u
n u u
n
u
n
n
n
+
•
=
=
+
=
+
= +
1
1
1
which is the required Inductive step to be proved.
Hence we have | | | |.
u
n u
n
=
20
Theory of Automata, Formal Languages and Computation