Induction Proof on String

1,142

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

Share:
1,142

Related videos on Youtube

j226
Author by

j226

Updated on May 03, 2020

Comments

  • j226
    j226 over 3 years

    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.

    • ShyPerson
      ShyPerson over 8 years
      Hint: work on your basis cases on the empty string first. What basis cases can you identify?