Self doubt in TOC

Question

Suppose in question we are given the language is Turing Recognizable , can I consider it a CFL or Regular?

Comments

@Parshu think it this way. A  Delhiite (CFL in your case) in an Indian (Turing Recognizable). But an Indian (Turning Recognizable) may or may not be a Delhiite (CFL) since Indians is a much larger group when compared to Delhiite.

---

Turing recognizable language :-

for TRL there exits a TM which halts on every input form L but may or may not halts on input out of L...

therefor you can't consider it as CFL/R but Recursive Enumerable....

---

I think all regular, CFL and CSL can be recognised by TM. TM will definitely halt on these. But if we think the same for REC it is not true as it may possible that TM does not all on some rec languages.

Please let me know if I am wrong.

Answer 1

All regular, CFL, and CSL are recursive. But vice versa is not true.

By this logic you can't.

Answer 2

according to  my assumption, if a language is TM recognizable then its an completeness property

this COMPLETENESS PROPERTY is DECIDABLE for only Regular laguages

so," if a language is TM recognizable " its better to choose   REGULAR language.

thats my advise

Comments

A TM can recognise all type1, type2 and type3 language. Which means that the turing machine can recognise all regular, CFL and CSL. Why to go with only regular.

Please explain.