I've always felt that there's no "canonical" automata for recognising context-sensitive languages. Much like there's DFA for regular, PDA for context-free and Turing machines for RE.

I'm aware of LBA, but that's a finite restriction of Turing machines. In my view, it doesn't really stand on its own.

I once read a paper which gave a very interesting alternative, but I can't find it anymore. A link to that paper would be great, but I'd appreciate something more substantive too.


1 Answer 1


Here is an alternative model:

Benedek Nagy: Left-most derivation and shadow-pushdown automata for context-sensitive languages, ICCOMP'06: Proceedings of the 10th WSEAS international conference on Computers, pp. 1015-1020.

  • 1
    $\begingroup$ Oh, wow. It's different from the paper I expected, but it's still very good. It's nice to know there are multiple alternatives. $\endgroup$ Dec 24, 2021 at 16:14

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.