Given a set X and an operation op, X is closed under op, if for any x and y in X

ID: 3740503 • Letter: G

Question

Given a set X and an operation op, X is closed under op, if for any x and y in X, (x op y) is also in X

a. N = {1,2,3,….} is closed under multiplication (Sipser p. 45). Explain (one sentence)

b. N is NOT closed under division. Explain

if X = {L : L is a finite language over {0,1},

c. List two languages in X

d. is X closed under union?

e. is X closed under concatenation?

if X = {L : L is a language over {0,1} and all strings in L have prime length},

f . List two languages in X

g. is X closed under intersection?

h. is X closed under concatenation?

ans)

a) given set N ={1,2,3...} is closed under multiplication

say any values from N operated with multiplication 3*1 result is in N,9*10 = 90 is in N so closed under multiplicaion.

b) N is not under division

say (3,2) in N, 3/2=1.5(not in N ) similarly 111/10 = 11.1 which is n't in N so not closed under division0,1

c) X is finite languages over L = {0,1}

languages in X = {00},{01},{11},{1,0}{010011...,11110000... any finite combinations are languages in X.

d) yes X is closed under union

union is language(l1) + language(l2) i.e from c) above say 00+1 -> 001 is in X so X is closed under union

e) yes X is closed under concatenation say l1(00), l2(0101) l1.l2 =(000101) so closed under cancatenation

f)X is a language over L whose strings are of prime length i.e 1,3,5,7,11,13..

X is not closed under intersection because say x1 =(1),x2=(000) - > x1^x3 is not in L

g) X is not closed under concatenation why because x1.x2 =(1000) 4 string length which is not prime length.

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