GATE Overflow | Mock GATE | Test 1 | Question: 56

Question

Consider the following language $L$:
$L=\{<M,x,k> \mid M \text{ is a Turing Machine and M does not halt on x within k steps} \}$
The language family to which $L$ belongs is not closed under?

• A. Intersection
• B. Homomorphism
• C. Set Difference
• D. Complementation

Answer 1

$\text{L={<M,x,k>∣M is a Turing Machine and M does not halt on x within k steps}}$

L is a recursive language, There are 3 inputs TM, K and x to the UTM, we can run the UTM for a given input and find whether the given TM halts on x with in k steps, if it halts we can ignore it and if it doesn't then we can keep it inside our language.

Hence, it's possible to make a total Turing machine for this language, so it's a $Decidable$ problem, So, L is recursive.

Recursive languages are not closed under $Homomorphism$, So, (B) is the correct option!

Note that, Recursive languages are closed under $intersection$ and $complement$, and $A-B = A∩B'$ Hence, Recursive languages are closed under set difference.

Comments

No language [class] is closed under set difference? How come? $A - B = A \cap \overline B.$ Recursive family is closed under intersection and complement and so set difference too.

---

@Arjun sorry :( i confused set difference with subset property :(, yes every language which is closed under intersection and complement will be closed under set difference.

---

Is this table correct?

---

@pallaviamu

follow this one:https://gatecse.in/closure-property-of-language-families/