Talk:Context-sensitive language

From Wikipedia, the free encyclopedia

Philosophy Portal

This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details.

???

This article has not yet received a rating on the quality scale.

???

This article has not yet received an importance rating on the importance scale.

Additional information:

Related task forces (core areas):
	Logic

I think it is not quite illuminating enough to say you can prove that the languages of strings of prime number length is context-sensitive by building an LBA for it. This is strictly true, but I can build an LBA to decide any language that is context-sensitive, but also context-free, or even regular.

If the point is to say why prime numbers are context-sensitive and not simpler then we need to show why you can't recognize them using a PDA or simpler machine.

--74.194.27.5 (talk) 03:48, 5 December 2007 (UTC)

Added a note that explains how to prove the language is neither regular nor context free. That should make the example more illuminating. -- Vantelimus (talk) 11:06, 31 December 2007 (UTC)

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)