1
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Aug 29, 2019 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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