<p>Here is an alternative model:</p>
<p>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.</p>

CC BY-SA 4.0
2021-12-24T16:14:02.433Z
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.
William Turner
CC BY-SA 4.0
2021-12-23T20:52:07.723Z
2021-12-23T20:52:07.723Z
Hermann Gruber
<p>I've always felt that there's no &quot;canonical&quot; automata for recognising context-sensitive languages. Much like there's DFA for regular, PDA for context-free and Turing machines for RE.</p>
<p>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.</p>
<p>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.</p>

<automata-theory><grammars><space-bounded>
Alternative to LBA for recognising context-sensitive languages
William Turner
# Alternative to LBA for recognising context-sensitive languages

(Asked by: username_0 on 2021-12-21)

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.

**Tags:** automata-theory, grammars, space-bounded


---

## 1 answers

### Answer by username_1 on 2021-12-23. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

