Solutions-a12021 - assignment 1 PDF

Preview

Summary

Let ∑={a;b}. (5 marks) a) Give an example of a language S over ∑ such that the language S* has more six-letterwords than seven-letter words.Answer: 1 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...

Description

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...