I have a question about the equivalence of different automata. I looked up the similiar questions but sadly none of them are exactly, what I need or am looking for.

I know some of these are equivalent ( or not ) but for which language class pairs does a real inclusion apply?

DFA = NFA ⊋ ? DPDA ≠ PDA ⊋ ? LBA = DTM = NTM

I want to know, if this is correct or not.

Hint:" C is the class of all languages accepted by a C-type machine" - If this is important.

I apologize, if my question isn't in a correct format, therefor forgive me, I am trying to settle in.


Linear-bounded automata accept the class of context-sensitive languages. In contrast, Turing machine (deterministic as well as nondeterministic) accept the class of recursive languages. Every context-sensitive language is recursive, but the converse doesn't hold. For example, the halting problem for nondeterministic Turing machines running in space $n^2$ is not context-sensitive by the nondeterministic space hierarchy theorem.

  • $\begingroup$ I appreciate the longer answer, thanks again. I gave you an upvote, even if it's not visible. ( since I am new ). $\endgroup$ – Seran Aug 29 '19 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.