Semi-decidability Vs Undecidability

Question

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?

Comments

Complete term is new to me

where u got the term?

---

I saw it here

https://gateoverflow.in/196380/dcfl-completeness-problem

 

---

7 and 9 are undecidable.

Rest all are semidecidable.

Not sure about 8.

 

The semidecidability comes due to halting problem of turing machine. It halts for all the members, but may or may not halt for non members.

The undecidability comes if turing machine does not halt even for members.

A problem P is decidable, only if it is within REC circle of Chomsky hierarchy.

A problem which is within RE, but not within REC is semidecidable, I.e., the Turing Machine may not halt for non members.

Now, if we take complement of this language, it will become undecidable, as it will have to accept non members, and it may not halt for them.

When a language is generated by unrestricted grammar, and when we see decidability table, some problems are decidable and some are semidecidable (membership, emptiness, finished, equivalence, regularity, ambiguity, completeness, disjointness). Now, if we take complement of these semidecidable problems, they become undecidable.