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

© Copyright 2023 ExpyDoc