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.

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

Hint. Very often, induction on strings means induction on the length of a string.

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$.

You may now try this method on your exercise.

(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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.