1) Let ¡Æ={a;b}. (5 marks)
a) Give an example of a language S over ¡Æ such that the language S* has more six-letter
words than seven-letter words.
Answer: 1.5 marks
{aa,bb} or {ab,ba} or {aa,ab}, {aaaaaa}….
For {aa,bb} :
The length of all strings in S* is even so there is no seven-letter words in S* six-letter words such as aaaaa, aaaabb, aabbaa, aabbbb, ….
b) Give an example of a language S over ¡Æ such that the language S* has more six-letter words than eight-letter words.
Answer: 1.5 marks
{aaa,bbb} or {aab,aaa} ….
There is no eight-letter words in S*
c) Does there exist an S* over ¡Æ such that it has more six-letter words than twelve-letter words? Explain briefly why or why not.
Answer: 2 marks for correct explanation
There is not. since for every six-letter word in S* such as ¡°w¡±, we can have ¡°ww¡± in S* as well, which is a twelve-letter word.
2) Let ¡Æ={a;b}. (5 marks)
a) Consider the language S = {aa; ab; ba; bb}. Describe the language S* using English
phrases.
Answer: 1.5 marks
All strings of a¡¯s and b¡¯s with even length
b) Give an example of a language S such that S* only contains all possible strings of a¡¯s and b¡¯s that have length divisible by 3.
Answer: 2 marks (should contained all 8 combinations) {aaa,aab,aba,abb,bbb,bba,bab,baa}
c) Let S be all strings of a¡¯s and b¡¯s with odd length. Describe S* using English phrases.
Answer: 1.5 marks
All strings of a¡¯s and b¡¯s (all non-empty words)
3) Prove that for all sets S, (S+)+ = S+.
Answer = 5 marks (2.5 each part)
We need to show that (S+)+ is the subset of S+ and vise versa.
1. If ¡®w¡¯ is in (S+)+ then it is derived from factors of S+. Each of these factors is then derived from factors of S. Thus, ¡®w¡¯ is from the factors of S, so ¡®w¡¯ is in S+. As a result,
(S+)+ is the subset of S+.
2. By definition, (S+)+ contains all possible concatenations of S+, including the words
existing in S+. As a result we can see that S+ is the subset of (S+)+. So we can conclude (S+)+ = S+.
4) Let ¡Æ={a;b}.
a) Consider the following incorrect recursive definition of the PALINDROME language:
Rule 1 a and b are in PALINDROME.
Rule 2 If x is in PALINDROME, then axa and bxb are in PALINDROME.
This language contains only words of odd length. Fix it so that it contains all words of PALINDROME.
Answer : 2.5 mark. (reduce 0.5 marks if they add ¡®aa¡¯ and ¡®bb¡¯ to rule one as ¦« will be missing from the answer)
We just have to add null string to rule one.
Change rule one to: Rule 1 ¦« , a, b are in PALINDROME.
b) Give a recursive definition for the language EVENPALINDROME of all palindromes of even length. (Note: 0 is an even number.)
Answer : 2.5 mark. (should not forget null string) Rule 1 ¦« is in EVENPALINDROME
Rule 2 If x is in EVENPALINDROME, then axa and bxb are in EVENPALINDROME.
5) Give recursive definitions for the following languages over the alphabet {a; b}. Do not use any restrictions on your rules.
a) The language Q5a of all words containing the substring aa.
Answer : 2.5 mark. (reduce mark (depending on the answer) if it accepts more or less) Rule 1 aa is in Q5a
Rule 2. If x is in Q5a so does ax, xa, xb,bx
b) The language Q5b of all words not containing the substring aa.
Answer : 2.5 mark (reduce mark (depending on the answer) if it accepts more or less) Rule 1 ¦« ,a, b is in Q5b
Rule 2 If x is in Q5b so does xb, xba