# Induction Proof on String

Formally prove the correctness of the union construction as follows. Let

• $M_1$ and $M_2$ be the two $\lambda$-NFA's constructed for $R_1$ and $R_2$ and let
• $N$ be the $\lambda$-NFA constructed so that $L(N) = R_1 + R_2$. Let
• $w$ be a string such that ${\Delta_N}^{*}(q,w,f)$, where
• $q$ is the start state and
• $f$ is the final state.

Prove that either ${\Delta_{M_1}}^{*}(q_1, w, f_1)$ or ${\Delta_{M_2}}^{*}(q_2, w, f_2)$. Use induction on all strings $w$.

I've never done induction on strings before, so I'm a bit confused. I was thinking about using the empty string as the base case, but I'm not sure what I can even say about that. If there's a path from $q$ to $f$ by way of $\lambda$, then obviously this must be the case for one of the two $M$ NFAs... but why? How can I explain this?

Getting past the base case, I'm imagining the proof showing all types of strings $w$: $\text{'a'}$, $\text{'ab'}$, $\text{'a + b'}$, and $\text{'a*'}$ succeeding in the same way as the base case sufficing to prove this for all strings? Thanks for any help, I'm reading and re-reading this section in the book and I'm getting nothing out of it.

• Hint: work on your basis cases on the empty string first. What basis cases can you identify? – ShyPerson May 1 '15 at 17:10

Here is a general scheme to prove that some property $P$ holds for all words of $A^*$. As I said, you prove the result by induction on the length $n$ of a word $u$. You first prove $P$ for $n = 0$ (which means that $u$ is the empty word, right?). Then you suppose that $P$ holds for all words of length $\leqslant n$ and you prove $P$ for a word $u$ of length $n+1$. Very often$^{(1)}$, you start by observing that $u = pa$, where $p$ is the prefix of length $n$ of $u$ and $a$ is a letter and you apply the induction step on $p$.
(1) In some cases, you may have to write $u=as$, where $s$ is the suffix of length $n$ of $u$ and $a$ is a letter and apply the induction step on $s$.