Always remember that a language is a set of strings, so **yes** you can apply set difference property. See Arjun Sir's answer: https://gateoverflow.in/2190/gate2010-17?show=2381#a2381

3 votes

If a language(L1) is Recursive enumerable (RE) and L2 is Recursive (REC) , then what will be L1 - L2 ? Can we directly use set difference property or do the so called intersection method i.e L1 - L2 = L1 ∩ L2 .

0

**yes** you can apply set difference property. See Arjun Sir's answer: https://gateoverflow.in/2190/gate2010-17?show=2381#a2381

1 vote

L1 = RE

L2 = REC

L1-L2 = L1 ∩ L2^{c }= RE ∩ REC = RE ∩ RE = RE

As, REC is closed under complement and RE is closed under intersection.

0

L1 = RE , L2 = REC , all REC Recursive are Recursive enumerable so L2 = RE

now as per closure property of languages in case of SET DIFFERENCE , RE ARE NOT CLOSED UNDER SET DIFFERENCE .so RE - RE NOT EQUAL TO Recursive enumerable . SO how you get RE - RE = RE

now as per closure property of languages in case of SET DIFFERENCE , RE ARE NOT CLOSED UNDER SET DIFFERENCE .so RE - RE NOT EQUAL TO Recursive enumerable . SO how you get RE - RE = RE

0

Why you are using L1 - L2 = L1 ∩ L2 . , why not directly apply SET DIFFERENCE PROPERTY , THAT IS IN CASE OF Recursive enumerable RE- RE = NOT EQUAL TO RE.

Closure Properties of Languages

Property | Regular | CFL | DCFL | CSL | Recursive | RE |

Union | Yes | Yes | No | Yes | Yes | Yes |

Intersection | Yes | No | No | Yes | Yes | Yes |

Set Difference | Yes | No | No | Yes | Yes | No |

Complementation | Yes | No | Yes | Yes | Yes | No |

Intersection with a regular lang. | Yes | Yes | Yes | Yes | Yes | Yes |

Concatenation | Yes | Yes | No | Yes | Yes | Yes |

Kleen Closure | Yes | Yes | No | Yes | Yes | Yes |

Kleen Plus | Yes | Yes | No | Yes | Yes | Yes |

Reversal | Yes | Yes | Yes | Yes | Yes | Yes |

Homomorphism | Yes | Yes | No | No | No | Yes |

ϵ-free Homomorphism | Yes | Yes | No | Yes | Yes | Yes |

Inverse Homomorphism | Yes | Yes | Yes | Yes | Yes | Yes |

Substitution | Yes | Yes | No | No | No | Yes |

ϵ-free Substitution | Yes | Yes | No | Yes | Yes | Yes |

0

It means that RE - RE is not equal to RE is FALSE . IT SHOULD BE , RE - RE = RE ,

So Recursive enumerable (RE) ARE CLOSED UNDER SET DIFFERENCE , Simply say it is correct or not

So Recursive enumerable (RE) ARE CLOSED UNDER SET DIFFERENCE , Simply say it is correct or not

0

This conclusion is wrong!! RE-RE=RE is not true because RE is not closed under Complement.

in the original question we are subtracting REC and REC is closed under Complement.

in the original question we are subtracting REC and REC is closed under Complement.

0

Closure Properties of Languages

Property | Regular | CFL | DCFL | CSL | Recursive | RE |

Union | Yes | Yes | No | Yes | Yes | Yes |

Intersection | Yes | No | No | Yes | Yes | Yes |

Set Difference | Yes | No | No | Yes | Yes | No |

Complementation | Yes | No | Yes | Yes | Yes | No |

Intersection with a regular lang. | Yes | Yes | Yes | Yes | Yes | Yes |

Concatenation | Yes | Yes | No | Yes | Yes | Yes |

Kleen Closure | Yes | Yes | No | Yes | Yes | Yes |

Kleen Plus | Yes | Yes | No | Yes | Yes | Yes |

Reversal | Yes | Yes | Yes | Yes | Yes | Yes |

Homomorphism | Yes | Yes | No | No | No | Yes |

ϵ-free Homomorphism | Yes | Yes | No | Yes | Yes | Yes |

Inverse Homomorphism | Yes | Yes | Yes | Yes | Yes | Yes |

Substitution | Yes | Yes | No | No | No | Yes |

ϵ-free Substitution | Yes | Yes | No | Yes | Yes | Yes |