Decidable / Undecidable

Question

1. Given a regular language, does the language contain any string at all. 
2. Given a regular language, does the language contain infinite number of strings.
3. Given a recursive language, does the language contain infinite number of strings.
4. Given a recursive language, does the language contain any string at all. 

Comments

I think the first one should be decidable.

We can give the algo as:

1. Since it is a regular language, we can create a DFA for it.
2. In the DFA, check if there exists any path from the initial state to final state.
3. If no path exists, accept.
4. Else, reject.

For the second one, we can create a regex and the language is infinite iff there exists a variable of the form A*, where A is a non-empty string.

---

goxul i agree and what about 3 and 4?

---

I think four should be undecidable too.

Given, the language is recursive. -> There exists a halting TM for it.

Now to show that the language of the halting TM contains no strings, we'll have to show that when all possible strings are run on the halting TM, it accepts none of them. Since this will take infinite time, the problem has to be undecidable.

Although, I am not sure. If I find something better, I'll let you know.

---

yes, i also think 1^st and 2^nd will be decidable and 3^rd and 4^th will be undecidable.

Answer 1

all are decidable becoz for regular language and recursive languages there exist a membership algorithim so we can decide wheather it is infinite or finite.

\