Example of induction on length of a string

Example of induction on length of a string
Suppose that you have the following rules for words in a language L:
• The word “E” is the only word in L that is of length 1.
• Other than E, words in L are one of the following:
1. a word in language L ending in a consonant, followed by another consonant
2. a word in language L ending in a vowel, followed by another vowel1
1. Prove by (weak) mathematical induction that every word in L consists solely
of vowels.
2. Proof will be by induction on the length k of a word in language L.
3. Base Case: Word w is of length 1. Then w = E and w consists solely of vowels.
4. Induction Hypothesis: If a word in L is of length k, then that word consists
solely of vowels.
5. Induction Step: Prove that if a word in L is of length k + 1, then that word
consists solely of vowels.
Suppose that word w is of length k + 1, that is |w| = k + 1. Then w = yxi ,
where |y| = k and xi is a letter.
• Case 1: xi is a consonant; then the last character of y is also a consonant
by the rules of language L. But |y| = k and so by the induction hypothesis,
y consists solely of vowels. So this case is not possible (i.e. there can be
no words in L that fit this case).
• Case 2: xi is a vowel; then the last character of y is vowel by the rules of
language L. |y| = k and so by the induction hypothesis, y consists solely
of vowels. Thus since w is the concatenation of y and the vowel xi , w must
consist solely of vowels.
So if a word in language L is of length k + 1, then the word consists only
of vowels.
6. Thus by induction on the length of a word in language L, we conclude that
every word in L consists solely of vowels.
1
Before you try the proof, write some short strings and see if they fit the rules to get an intuitive
sense of the language.
1

Download Report