Complexity

Question

How to decide the complexity of any language?

Comments

There is only one language in Chomsky hierarchy which talks directly about complexity- and that is CSL which requires space complexity to be linear. This question is yet another ACE epic.

---

Don't know why they ask such questions?

There was another question that asks What is the space complexity of recursive languages?

Answer 1

Don't know what that complexity is about.

The question says that TM halts on every input i.e it outputs Yes for all strings belonging to L and NO for those that doesn't.

It implies its a halting TM which accepts Recursive language. (Recursive is superset of CFL and CSL).

For Recursively Enumerable languages, TM halts for acceptable strings but doesn't halt always if string doesn't belong to L and goes into infinite looping.

So answer is Recursive language

Comments

Why not all other's then??

---

Halting TM can recognize CSL,CFL,RL,Regular language. But we have different machines for them Regular(FA),CFL(PDA),CSL(LBA),Recursive language(Halting TM). So in generalised manner Halting TM can accept Regular,CSL,CFL,Recursive language.