Talk:Context-sensitive language

From Wikipedia, the free encyclopedia

Is the following correct?:

• Finite state machines accept regular languages

• Non-deterministic FSMs with a single stack accept context-free languages

• FSMs with two stacks are equivalent to Turing machines.

If that's the case, is there a definition of context-sensitive languages in terms of augmented FSMs?

That's correct. If you like to, you could regard linear bounded Turing machines (the acceptance devices for CSL) as non-deterministic FSMs with two stacks that are both linear bounded. --141.2.6.22 16:07, 30 March 2006 (UTC)