Talk:Context-sensitive grammar

(Contrary to a previous version of this article, the decision problem is not undecidable.)

Natural Language?

The article says that Chomsky invented CSG for natural languages. Are CSGs really used in linguistics? I've only seen context-free grammars (or some mild extensions) in that context.

Yes, context-sensitive rewrite rules have been used in linguistics, but I do not know whether they are still in use today. Rp 13:36, 25 July 2007 (UTC)

Added by Paul Ogilvie: in computer science only algorithms have been developed that can easily parse context free languages. These are now common, such as the yacc compiler-generator, an algorithm that can parse a CFL-definition and generate a program that can regognizse the CF language. See Aho, Sethi, Ullman, Compilers - Principles, tools and technisques, 1986. No algorithms have been developed (to my knowledge) that can parse a CSL, except heuristically.

Yacc doesn't parse arbitrary context-free languages, but only LALR(1) ones. An example of a general context-free parsing framework is ASF+SDF. Rp 13:36, 25 July 2007 (UTC)

Yes, there are natural languages that are not context free (take for example verbs in Swiss German). The algorithm for parsing CSL is quite straightforward (the complexity is high, obviously).

Contradicts definition?

The example has the rule

   cB → Bc

but that means α = c on the left-hand side, but α is empty on the right-hand side? Or is the example simply using the alternative definition of context-sensitive? As you can see, I've only studied context-free grammars so far :)

I think the example is using a monotonic grammar for the sake of simplicity (as an equivalent context-sensitive grammar can be constructed, but it probably wouldn't be as simple).

A monotonic grammar and a context-sensitive one isn't necessarily the same, so maybe the difference between the grammar and the generated language should be further illuminated. --Bernhard Bauer 00:46, 28 July 2006 (UTC)

I think that the following grammar will work:

S -> aRc

R -> aRT | b

bTc -> bbcc

bTT -> bbUT

UT -> UU

UUc -> VUc -> Vcc

UV -> VV

bVc -> bbcc

bVV -> bbWV

WV -> WW

WWc -> TWc -> Tcc

WT -> TT

As you can see, it is rather more complicated than the one in the article. 66.218.45.98 00:39, 20 January 2007 (UTC)

There is a more standard definition of context sensitive rules (used in most textbooks): a rule x -> y is context sensitive iff |x| <= |y|.

Why should people believe those two definitions are equivalent? Liberulo (talk) 21:06, 30 December 2012 (UTC)

UPDATE: This paper has a proof of the equivalence of the context-sensitive languages and monotonic languages, but I cannot vouch for its correctness. Liberulo (talk) 21:20, 30 December 2012 (UTC)

According to this definition, Aa -> aA, a is terminal and A non terminal symbol, is context sensitive. Moreover, the authors claim that these 2 definitions are equivalent! How can this be possible? —Preceding unsigned comment added by 85.73.192.119 (talk) 21:01, 11 September 2008 (UTC)

I second this question: I'd like to know if and how these two definitions of CSGs are equivalent. Liberulo (talk) 21:06, 30 December 2012 (UTC)

UPDATE: Look here, see if this paper contains a satisfactory proof. Liberulo (talk) 21:20, 30 December 2012 (UTC)

This is the definition I have seen, for example in Peter Linz, 'An Introduction to Formal Languages and Automata (2nd Ed.)', Chapter 11.3 (1997). Note that if the empty word is to be in the language that needs to be directly specified as a special case, as 'non-contracting' rules obviously can't specify it. The reference Linz cites 'for example' to show that such a grammar is indeed 'context-sensitive' in the sense of the current state of this article is A. Salomaa, 'Formal Languages' (1973). If anyone can track this down it might be the best reference. 150.203.209.134 (talk) 05:08, 18 September 2013 (UTC)

Wrong grammar for language $\{a^{n}b^{n}c^{n}:n\geq 1\}$

The grammar given for the language mentioned is not right according to the definition. Moreover the rule CB -> BC makes the grammar unrestricted.

I suggest the following context-sensitive grammar which does apply to the definition given.

1. $S\rightarrow aSBC$
2. $S\rightarrow aBC$
3. $CB\rightarrow HB$
4. $HB\rightarrow HC$
5. $HC\rightarrow BC$
6. $aB\rightarrow ab$
7. $bB\rightarrow bb$
8. $bC\rightarrow bc$
9. $cC\rightarrow cc$

Again the derivation for "aaa bbb ccc" is:

$S$

$\Rightarrow _{1}aSBC$

$\Rightarrow _{1}a{\boldsymbol {aSBC}}BC$

$\Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC$

$\Rightarrow _{3}aaaB{\boldsymbol {HB}}CBC$

$\Rightarrow _{4}aaaB{\boldsymbol {HC}}CBC$

$\Rightarrow _{5}aaaB{\boldsymbol {BC}}CBC$

$\Rightarrow _{3}aaaBBC{\boldsymbol {HB}}C$

$\Rightarrow _{4}aaaBBC{\boldsymbol {HC}}C$

$\Rightarrow _{5}aaaBBC{\boldsymbol {BC}}C$

$\Rightarrow _{3}aaaBB{\boldsymbol {HB}}CC$

$\Rightarrow _{4}aaaBB{\boldsymbol {HC}}CC$

$\Rightarrow _{5}aaaBB{\boldsymbol {BC}}CC$

$\Rightarrow _{6}aa{\boldsymbol {ab}}BBCCC$

$\Rightarrow _{7}aaa{\boldsymbol {bb}}BCCC$

$\Rightarrow _{7}aaab{\boldsymbol {bb}}CCC$

$\Rightarrow _{8}aaabb{\boldsymbol {bc}}CC$

$\Rightarrow _{9}aaabbb{\boldsymbol {cc}}C$

$\Rightarrow _{9}aaabbbc{\boldsymbol {cc}}$

--Gerel (talk) 15:20, 19 December 2008 (UTC)

• Thanks. Much simpler than the one I cooked up. Ben Standeven (talk) 07:22, 13 February 2009 (UTC)

This might be a dumb question, but is a context-sensitive grammar allowed to "crash"? As in, end up with non-terminals and have no valid rules to follow. If it is not, then I think I found a derivation that would cause it to crash. Again, sorry if this is legal, I'm just learning about these now and it was not mentioned in class; my assumption was that a valid grammar had to always return a string of all terminals. Here's the derivation that would "crash" it:

$S$

$\Rightarrow aSBC$

$\Rightarrow a{\boldsymbol {aBC}}BC$

$\Rightarrow a{\boldsymbol {ab}}CBC$

$\Rightarrow aa{\boldsymbol {bc}}BC$

Again, sorry if this is a dumb question, I just had to answer this question for a problem set and came up with a different answer (that I believe is correct), that does not ever "crash" like this one.

• It seems that the grammar does not produce only $\{a^{n}b^{n}c^{n}\}$. For example this grammar can produce "aaa bb cccc":

$S$

$\Rightarrow _{1}{\boldsymbol {aSBC}}$

$\Rightarrow _{1}a{\boldsymbol {aSBC}}BC$

$\Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC$

$\Rightarrow _{3}aaaBCB{\boldsymbol {HB}}C$

$\Rightarrow _{3}aaaB{\boldsymbol {HB}}HBC$

$\Rightarrow _{4}aaaBHB{\boldsymbol {HC}}C$

$\Rightarrow _{4}aaaB{\boldsymbol {HC}}HCC$       <--- ("H" in question below was introduced here)

$\Rightarrow _{5}aaaBHC{\boldsymbol {BC}}C$

$\Rightarrow _{3}aaaBH{\boldsymbol {HB}}CC$

$\Rightarrow _{4}aaaBH{\boldsymbol {HC}}CC$

$\Rightarrow _{5}aaaBH{\boldsymbol {BC}}CC$       <--- "H" stemming from a "B" ...

$\Rightarrow _{4}aaaB{\boldsymbol {HC}}CCC$       <--- but transformed to "C"

$\Rightarrow _{5}aaaB{\boldsymbol {BC}}CCC$

$\Rightarrow _{6}aa{\boldsymbol {ab}}BCCCC$

$\Rightarrow _{7}aaa{\boldsymbol {bb}}CCCC$

$\Rightarrow _{8}aaab{\boldsymbol {bc}}CCC$

$\Rightarrow _{9}aaabb{\boldsymbol {cc}}CC$

$\Rightarrow _{9}aaabbc{\boldsymbol {cc}}C$

$\Rightarrow _{9}aaabbcc{\boldsymbol {cc}}$

(Or am I missing something?)

It seems however that the following grammar works:

1. $S\rightarrow aSBC$
2. $S\rightarrow abc$
3. $cB\rightarrow Bc$
4. $bB\rightarrow bb$

but it does not follow the rule given in the page. Ref: http://www.cs.cmu.edu/~./FLAC/pdf/ContSens-6up.pdf‎

Metaxal (talk) 13:33, 11 February 2014 (UTC)

I agree with your derivation of aaabbcccc. My informal understanding of rules 3-5 is that they are used to swap BC to CB, and that the total count of Bs and Cs can't be changed by these rules if H is counted as B or C in an appropriate way (i.e. 3: CB→^H
_CB, 4: ^H
_CB→^H
_BC, 5: ^H
_BC→BC). Based on that, I tried to locate the "error", and came up with my flagging of your derivation above. The orginal idea of the grammar's author might have been that the "meaning" of an H (i.e. whether it is to be counted as B or as C) is always determined from the nonterminal immediately right to it: count H as B in HC, count H as C in HB. However, in your derivation, the nonterminal immediately right to the "critical" H is changed from C to B due to some unexpected swapping.

I wonder what the source of the flawed grammar is; it doesn't appear in Hopcroft+Ullman 1979, which is the only text on CSG I have. If it remains unsourced, it should eventually be removed, anyway. When I've time, I could elaborate H+U's $a^{2^{i}}$ example as a replacement.

I had a look at your Ref: Sutner has (on slide 4-->p.1) the same restriction as the wikipedia article, and his rule cB→Bc doesn't satisfy them (the left and right embedding context of B on the rule's left-hand side, viz. c and ε, respectively, should reappear on its right-hand side, but c doesn't). Maybe that is what Sutner expects as an answer to his question "Right?" on slide 7-->p.2. Moreover, not even the Kuroda normal form (slide 11-->p.2) fits into the scheme. Probably Sutner implicitly used the notion of a Noncontracting grammar. The wikipedia article contains his $a^{n}b^{n}c^{n}$ grammar as well as the Kuroda NF, and claims equivalence to CSG. - Jochen Burghardt (talk) 09:14, 12 February 2014 (UTC)

I got a look into the Mateescu & Salomaa (1997) cited by the Noncontracting grammar article and explained their transformation of noncontracting grammars to context-sensitive grammars, using the $a^{n}b^{n}c^{n}$ language as an example. The resulting grammar is different from that you revealed as flawed. - Jochen Burghardt (talk) 16:38, 12 February 2014 (UTC)

Today, I changed the $a^{n}b^{n}c^{n}$ grammar to the grammar from Noncontracting_grammar#Transforming into context-sensitive grammar, simplified by

• replacing   [a] by a,   [b] by b,   [c] by c,   Z₁ by W,   Z₂ by X,   and
• contracting the last four rules into bB → bb.

I hope the simplifications (and the source grammar) are correct; please cross-check. Apparently, Metaxal's above derivation of aaabbcccc doesn't work any longer now. - Jochen Burghardt (talk) 20:33, 1 April 2014 (UTC)

Looks good to me (I'm actually testing the grammar with random derivations), except maybe that some derivations can get stuck with the X non-terminal alone, making the branch invalid, like aaabbbcXc. Metaxal (talk) 15:58, 7 April 2014 (UTC)

Confusing

Using a grammar that contradicts the definition is highly confusing. What is a monotonic grammar?

I'm moving the definition to "monotonic" grammar to its own page. It's wrong to include it here, since this page is not about classes of grammars that happen to describe the contest-sensitive languages, but about context-sensitive grammers proper. Rp 13:38, 25 July 2007 (UTC)

HERE IS THE EASY ANSWER:

S → aSBC | abc
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc

The problem with your solution lies in the clause "S -> abc". As far as "abc" terminates your recursion, the structure "aabcBC" always gets created whenever you try to use recursion. The way to go is the usage of "S -> aBC", which is totally equivalent with the grammar in the Wiki page. --AdamDi (talk) 11:11, 29 April 2012 (UTC)

can you please explain this textbook problem

That why AB -> BA is not type 1 grammar —The preceding unsigned comment was added by Ra.ravi.rav (talk • contribs) 11:24, 18 February 2007 (UTC).

Is context-dependent the same thing as context-sensitive?

In the Turing completeness article, there is a redlink for context-dependent grammar. If that is the same thing as context-sensitive grammar, please fix the link. Paul Foxworthy (talk) 06:51, 10 June 2010 (UTC)

Formal Definition is not accurate

Specifically, "...and S does not appear on the right-hand side of any rule..." It seems the definition is not accurate. I would like to propose to recommend that the definition changes to a more accurate definition. A more accurate definition would be that the length of the left hand side of the formula is less than or equal to the length of the right hand side of the formula and the grammar cannot be represented in Chomsky Normal Form (i.e. there must be at least one string on the right that is non-contracting and has at least three symbols). Thus, the start symbol, can still appear on the right side of the rule as long as those conditions are met. Being able to include the start symbol on the right of the grammar would be able to simplify many essentially non-contracting context sensitive grammars with equivalent constructions where the the start symbol would not be allowed on the right.

Consider this quick and dirty example I thought of below, as, to write it without the start symbol would create many more production rules, but the start symbol on the right does not effect the fact it the grammar is essentially non-contracting and context sensitive.

1. $S\rightarrow \lambda$
2. $S\rightarrow aBC$
3. $S\rightarrow DSd$
4. $S\rightarrow DSe$
5. $B\rightarrow bb$
6. $C\rightarrow ccc$
7. $D\rightarrow dcc$

Not having the S symbol on the right is more of a rule of thumb or maybe a notation convention, not a formal definition. As it might be beneficial for the student to not write it as such for confusion resulting from the following situation:

1. $S\rightarrow \lambda$
2. $S\rightarrow SAB$
3. $A\rightarrow Saa$
4. $B\rightarrow SAb$

Which might appear to be context sensitive, but isn't, because it could be rewritten in Chomsky Normal Form.

Thus, I suggest we change or clarify the definition in this article.

reference: http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Context-sensitive_grammar.html

Jmark13 (talk) 16:50, 8 August 2013 (UTC)

Update:

After reading a few more texts on the matter It seems clear to me that the formal definition of a Context Sensitive grammar is simply the following:

Beginning of Formalism:

A context-sensitive grammar G is a quadruple (V, $\Sigma$, R, S) where V is a finite set of symbols, $\Sigma$ is the subset of V which contains only the terminal symbols and S is the start symbol in V, V$\notin \Sigma$.

R is a finite set of production rules in the form $\alpha \rightarrow \beta$ such that $\alpha$ and $\beta$ are members of V and $\Sigma$ and |$\alpha$| $\leq$ |$\beta$| where |x| is the length of x.

End of Formalism

Also, we should note that an essentially non-contracting non-context sensitive grammar is that context sensitive grammar which can be represented in such a way where no Start symbol appears on the right of the production Rule set. This is in contrast to what is written now, which states that a grammar cannot be context sensitive if there is a Start symbol on the right hand side of the production rule set which can go to the empty string. The actual formal definition of context sensitive grammars is broader based on the references cited.

Jmark13 (talk) 19:27, 9 August 2013 (UTC)

Hi Jmark13.

I don't think it's obvious why your references should be used to change the definition. Here are some other search results supporting the tendency of the current definition: [1], [2], [3].

However, I agree that the exceptional rule concerning $S\rightarrow \lambda$ is a bit informal (and even inaccurate, because it does not clearly state that S may appear on the right side, if there is no rule $S\rightarrow \lambda$). In addition, there are more quite important authors who defined context-sensitive grammars as non-contracting (Aho and Ullman, for example [4], and Ullman and John Hopcroft in Introduction to Automata Theory, Languages, and Computation). So it seems legitimate to adopt their definition in this article.

Still, since there are authors who distinguish context-sensitive grammars and monotonous grammars (e.g. Grzegorz Rozenberg and Arto Salomaa in [5]), I would object to replacing one definition by another. Rather than claiming that some authors additionally require non-contracting rules, it should be mentioned that the current definition implies non-contracting rules (except the exception) and that the generative power is the same (see my first link).

There's one thing I don't understand: Why do you mention Chomsky Normal Form as a negative criterion? Consider a grammar with two rules, $S\rightarrow AA$, and $A\rightarrow a$, the grammar clearly is context-sensitive according to both definitions, yet it is in CNF – or am I missing something?

--Zahnradzacken (talk) 22:57, 19 August 2013 (UTC)

Thank You, Zahnradzacken, I don't think you are missing anything, but I do think something in the formal definition of context-sensitive grammars is a bit ambiguous. And no, we should definitely not change the formal definition in so far as it agrees with the sources mentioned.

However, a less ambiguous definition of CSG would be one that would be formalized in terms of LBA, and be those re-writing rules that form the languages accepted by an LBA, since it has been proven that the languages produced are equivalent.

In terms of CNF, I was incorrect in my assertion, as languages produced by context free grammars is a strict subset of those produced by context sensitive grammars. I apologize for any confusion.

All this said, essentially non-contracting context sensitive grammars is itself a subset of uniform context sensitive grammars, which may be "mildly contracting" (not to be confused with mildly context sensitive) in that there is a contraction, but the length of the right hand side of every rule, even after contraction, is still strictly greater than or equal to the left... The languages produced by this definition should be obviously equivalent to those languages produced by essentially non-contracting grammars.

In my opinion, a set of grammar production rules should be in it's simplest form, i.e. the fewest amount of rules that produce all strings in the language. However, this often requires "mild contraction" on a set of rules that would otherwise be context-sensitive and essentially non-contracting. And while this might seem like splitting hairs here, there are a lot of results to theorems that depend on grammars that are deemed essentially non-contracting and context sensitive that would have to be re-proved for a "mildly contracting" context sensitive grammar, but despite the fact there is an S on the right, it should be obvious that these mildly contracting context sensitive grammars can be re-written as essentially non-contracting context sensitive grammars (just add more rules and replace each S symbol accordingly), and have an equivalent expressive power.

So, "What is true?" And if it is true that mildly contracting CSGs produces the same languages as essentially non-contracting CSGs, then the source definition, which includes that S cannot be on the right hand side, isn't a uniform or optimal definition, but applies only to essentially non-contracting CSGs. By eliminating this extra rule, and observing the class of difference between Recursively Enumerable languages with unrestricted grammars that are not CSGs with mildly contracting CSGs, we may simplify our Rule sets when appropriate and still have a CSG.

Anyway, if you see the logic above, and the benefits of being able to reduce some grammar rule sets to a mildly contracting CSG, then I do propose to at least add to the article that only some definitions add the extra requirement that S not occur on the right hand side and that these grammars are called "essentially non-contracting".

Jmark13 (talk) 00:49, 21 August 2013 (UTC)

On definitions and types of equivalence

There seems to be some confusion about the equivalence between context-sensitive grammars and noncontracting grammars. It's true that CSGs and noncontracting grammars are equivalent in the sense that they can describe the same sets of languages. But the definitions of the grammars aren't equivalent.

A definition is basically a sentence that talks about mathematical objects (formally speaking, it's a formula, as sentences are formulas without free variables). An example of a definition is "an integer x such that there exists integer y such that y*2 = x". The defined concept (even numbers) consists of those objects from the universe of discourse which yield a true sentence when substituted for x in the definition. Another definition of even numbers is "an integer x such that there exists integer y such that y + y = x". Those two definitions are equivalent. Any object either satisfies both definitions or doesn't satisfy either of them.

The definitions of CSGs and noncontracting grammars aren't equivalent, because e.g. the grammar with productions (S -> Bc; Bc -> Bd; Bd -> bd) satisfies the definition of noncontracting grammars but doesn't satisfy the definition of context-sensitive grammars, as the middle production changes a terminal symbol. That's that.

CSGs and nocontracting grammars are equivalent in their ability to describe languages. For any language L which is generated by a context sensitive grammar G, there exists a noncontracting grammar G' which generates language L. For any language L generated by a noncontracting grammar G, there exists a CSG G' which also generates G.

Some writers may equivocate between those two kinds of equivalence and say that two definitions are equivalent when in fact they define distinct concepts with equal expressive power. However, that should be limited to situations when the definitions differ in minor details and the expressive equivalence of the defined concepts is trivial to see. This is not quite the case here. 178.182.26.47 (talk) 18:19, 28 June 2014 (UTC)