Talk:Context-sensitive language

Untitled

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)

-- 2016-09-11: In the book titled "A Second Course in Formal Languages and Automata Theory" by Jeffrey Outlaw Shallit you can find proofs showing that the set of prime numbers over an unary alphabet are no a regular neither context-free language. Sallit also showed, however, that, over an unary alphabet, the class of regular and context-free languages coincides.

On the other hand, Juris Hartmannis, wrote a paper, published in 1968, titled "On the Recognition of Primes by Automata", in which it is proved that the set of primes number over a binary alphabet are no a regular neither context-free language. Moreover Hartmannis shows a proof of the fact of set of primes number over a binary alphabet is accepted by a LBA with a tape with three tracks; but his argument is based in the Church-Turing thesis and so, is not constructive. (see: http://rmc.library.cornell.edu/EAD/htmldocs/RMA03786.html),

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)

Decidable languages

are a proper superset of context-sensitive languages. Four Dog Night 00:23, 8 October 2007 (UTC)

Are they? The link points to recursive language, of which CSLs are a subset. SamuelRiv (talk) 09:26, 21 November 2007 (UTC)

IIRC, decidable languages is the same thing as recursive languages. –jonsafari (talk) 17:11, 21 November 2007 (UTC)

context sensetive language

well what is think is that the context sensitive language article should be merged with the context sensetive grammer this would be helpfull for the readers and these two topics are of the same phyloshopy . so i am in true favore of mergining of these two article context sensetive language and context sensetive grammer.(````) —Preceding unsigned comment added by Zades (talk • contribs) 12:40, 10 June 2010 (UTC)

I'm not sure, but if not it needs to be clarified. If clarification is too much work, then merging would be next-best. The problem is that the articles are short and circular; you can go around in circles between all the formal language and formal grammer (computer science) pages and apparently they make perfect sense to people who already understand it, but for a programmer used to informal descriptions and Turing machines, it is just circular nonsense and it isn't obvious, given a particular use case, if the problem could be solved with a particular formal language, or not. I've read half a dozen comp-sci pages with "context" in title and the closest I've found to actually defining what is meant by "context" are references to Chomsky linguistics; which is surely the source of the concept, but natural language linguistics is not a reasonable way for programmers to understand computer languages. That is true even for Perl users! 76.105.216.34 (talk) 18:26, 1 July 2016 (UTC)

context sensetive language

well what is think is that the context sensitive language article should be merged with the context sensetive grammer this would be helpfull for the readers and these two topics are of the same phyloshopy . so i am in true favore of mergining of these two article context sensetive language and context sensetive grammer. Zades 12:41, 10 June 2010 (UTC) —Preceding unsigned comment added by Zades (talk • contribs)

Least often used?

The claim in the introduction, that CSLs are the least often used in theory and practice, is that correct and is there some evidence for it? Aren't many (most?) programming languages context-sensitive? While they are often specified in context-free grammars, this leads to ambiguity which can only be resolved through context-sensitivity. — Preceding unsigned comment added by Jakmap (talk • contribs) 16:44, 4 December 2012 (UTC)

I removed the claim. Thanks for pointing it out! Unfortunately, the sentence dates back to 2002 and doesn't seem to have been questioned for more than 10 years. Since any CFL is a CSL, the claim is wrong anyway. Programming language syntax is usually defined by a CFG, yes, but why would that lead to ambiguity? --Zahnradzacken (talk) 22:47, 12 December 2012 (UTC)

Why CSL/CSG article split?

Is there a compelling reason for the articles Context-sensitive language and Context-sensitive grammar to be separate? Jcmckeown (talk) 21:09, 10 December 2015 (UTC)

@Jcmckeown: "Language" is not a synonym of "grammar." The syntax of a formal language is described by a formal grammar, but this does not make "language" and "grammar" synonymous. Jarble (talk) 17:48, 12 November 2019 (UTC)