587 views
0 votes
0 votes
Let L1 and L2 be 2 languages generated by an Unrestricted Grammar. I know that none of the following are decidable. But which of them are semi-decidable and which are Undecidable?
1. Whether L1 is Finite?
2. Whether L1 is Regular?
3. Whether L1 is Equivalent to L2?
4. Whether a string "x" is a member of L1 or not?
5. Whether L1 ∩ L2 is empty?
6. Whether L1 ∩ L2 is finite?
7. Whether L1 is complete?
8. Whether L1 is a subset of L2?
9. Whether (∑* - L1) is finite?
10. Whether L1 is Empty?

Please log in or register to answer this question.

Related questions

3 votes
3 votes
1 answer
4
rahul sharma 5 asked Aug 1, 2017
1,931 views
Semidecidable means RE or only but NOT REC? Can i say every semi decidable is undecidable?