2
$\begingroup$

I normally don't have any problems doing proofs by induction. However, in this case I'm struck because I have difficulty seeing how exactly I should approach the problem and construct the proof. Would anyone be so kind as to help me out of this abyss of ignorance and enter your world of enlightenment?

Define a set of "babble strings" inductively, as follows:

  • $\textbf{"ba"}$ is a babble string.
  • If $\textbf{s}$ is a babble string, so is $\textbf{"ab"}$$\cdot$$s$.
  • If $\textbf{s}$ and $\textbf{t}$ are babble strings, so is $\textbf{s $\cdot$ t}$.

Prove by induction that every babble string has the same number of a's and b's, and that every babble string ends with an "$\textbf{a}$".

$\endgroup$
5
$\begingroup$

What you want here is known as structural induction. You start with the strings mentioned in the ground case of the recursive definition and check that they have the property in question. Here there’s only one, ba, and it does: it has the same number of a’s and b’s, and it ends in a.

Then you show that the constructions permitted by the recursive definition preserve the property in question.

  • If s has the same number of a’s and b’s and ends in a, is this also true of ab·s? Yes: if s has, say, $n$ a’s and $n$ b’s, then ab·s has $n+1$ of each letter, and the last letter of ab·s is evidently the last letter of s, which by hypothesis is a.

  • If s and t both have the same number of a’s and b’s and end in a, is this also true of s·t? Again, it’s easy to show that the answer is yes.

Now you’re entitled to conclude that every babble string has the same number of a’s and b’s and ends in a. If you need a little more convincing, suppose that there were a babble string that did not have that property. Then there would be a shortest one without the property; call it u. Clearly u isn’t the initial babble string ba, so either u is ab·s for some babble string s, or u is s·t for some babble strings s and t. But both cases are impossible. For instance, if u were ab·s, then s would be a babble string shorter than u, so it would have the property, and the argument in the first bullet point above would show that u must have the property as well. The second bullet point takes care of the other possibility.

In this problem you could also use ordinary induction on the length of the babble string, but it’s a good idea to become familiar with the more general technique.

$\endgroup$
0

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.