5
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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$
    – William Turner
    Dec 24, 2021 at 16:14

Your Answer

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

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