1. Consider the language T* where T = {a,b,c}. How many words does this language

Question

1. Consider the language T* where T = {a,b,c}. How many words does this language have of length 2? Of length 3? Of length 4? Of length n?

2. Consider the language S* where S ={a,bb}. How many words does this language have of length 4? Of length 5? Of length 6? What can be said in general?

4. Consider the language T* where T = {aa, aba, baa}. Show that the words aabaa, baaabaaa, and baaaaababaaaa are all in this language. Can any word in this language be interpreted as a string of elements from T in two different ways? Can any word in this language have an odd total number of a's?

5. Consider the language PALINDROME over the alphabet {a,b}. List all word of even length with less than 5 letters in this language. List all words of odd length with less than 5 letters in this language.

6. Consider the language N* where N ={00, 01, 10, 11}. Give an English description of this language.

7. Give an example of a set T such that T* only contains all possible strings of c’s and d’s that have length divisible by 2.


8. Let S be all strings of 0’s and 1’s with odd length. What is S*.

Explanation / Answer

1. S * has 4 words of length 2 and 8 words of length 3. It appears that S * will have 2n words of length n. This can be proved by induction. Note that when n = 0 we have 1 word of length 0 and since 20 = 1 the basis step is satis?ed. For the inductive step we need to show that if S * has 2n words of length n then it will have 2n+1 words of length n + 1. All words of length n + 1 can be constructed by appending either an a or a b to each of the words of length n. Thus, increasing the word length by one increases the word count by a factor of 2. So there are 2n+1 words of length n + 1. 2. Strings of length 4 from S * : bbbb, bbaa, abba, aabb, aaaa. There are 5 strings of length 4 in S * . Strings of length 5 from S * : bbbba, bbabb, bbaaa, abbbb, abbaa, aabba, aaabb, aaaaa. There are 8 strings of length 5 in S * . Strings of length 6 from S * : bbbbbb, bbbbaa, bbabba, bbaabb, bbaaaa, abbbba, abbabb, abbaaa, aabbbb, aabbaa, aaabba, aaaabb, aaaaaa. There are 13 strings of length 6 in S * . To ?gure out the general case, for strings of length n, let’s examine how many strings there are of length n = 7. Since n is odd there must be at least one a in the string. So it’s possible for there to be 3 bb’s and 1 a, 2 bb’s and 3 a’s, 1 bb and 5 a’s or 0 bb’s and 7 a’s. We use comabinations to ?gure out the number of di?erent ways to place the a’s in each case and add these up: C (4, 3) + C (5, 2) + C (6, 1) + C (7, 0) = 4 + 10 + 6 + 1 = 21. 4. aabaa = (aa)(baa) baaabaaa = (baa)(aba)(aa) baaaaababaaaa = (baa)(aa)(aba)(baa)(aa) so we see that each of the these three words is in S * . It is not possible for any word in this language to be interpreted (factored) more than one way. Scanning from left to right the ?rst substring must match aa, aba or baa. If it matches any of these it will only match one of them. Place parentheses around the substring and restart the pattern matching from that point. Continuing in this fashion one will either ?nd that the string is not in S * or that there is only one way to interpret it. No string in S * can have an odd number of a’s since each string in S has an even number of a’s. Thus, all strings in S * , since they are formed from strings from S , will have an even number of a’s. 5. even length aa bb aaaa abba baab bbbb odd length a b aaa bbb aba bab 6. N* will be any string generated from 0 and 1. 7. T= {cd,dc,cc,dd} 8. S* will be string of 0 or 1 of even and odd.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.