This is the
talk page for discussing improvements to the
Context-sensitive grammar article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||||||||||
|
(Contrary to a previous version of this article, the decision problem is not undecidable.)
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.
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.
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).
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 :)
There is a more standard definition of context sensitive rules (used in most textbooks): a rule x -> y is context sensitive iff |x| <= |y|.
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)
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.
Again the derivation for "aaa bbb ccc" is:
-- Gerel ( talk) 15:20, 19 December 2008 (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:
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.
(Or am I missing something?)
It seems however that the following grammar works:
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)
Using a grammar that contradicts the definition is highly confusing. What is a monotonic grammar?
HERE IS THE EASY ANSWER:
S → aSBC | abc
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc
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).
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)
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.
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:
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 [1] [2] 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, , R, S) where V is a finite set of symbols, is the subset of V which contains only the terminal symbols and S is the start symbol in V, V.
R is a finite set of production rules in the form such that and are members of V and and || || where |x| is the length of x. [3]
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)
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)
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)
There is a problem with the grammar listed on the site as of now. As I'm a new user, I'm reluctant to edit the page without the consensus of the group.
This leads to problems like:
There is no available non-terminal to fix this; it looks like this could be fixed with the additional rule:
If there is agreement here, I'll happily edit the page. Pmeixner ( talk) 22:19, 7 August 2014 (UTC)
I just noticed too that the example contradicts the one given (from a reliable source) in Noncontracting grammar which doesn't have the extra non-terminals and rules. I don't have time right now to figure it all out, but I don't see anything wrong with simpler grammar right now. JMP EAX ( talk) 00:05, 16 August 2014 (UTC)
It seems that the distinction between Context-sensitive grammar and Noncontracting grammar is a source of confusion for many readers. Probably, many authors use the name "context-sensitive grammar" for what wikipedia calls a "noncontracting grammar"; the sentence "Some definitions of a context-sensitive grammar only require that for any production rule of the form u → v, the length of u shall be less than or equal to the length of v." in Context-sensitive grammar#Formal definition tries to make that clear, but it might be necessary to rephrase it (e.g. to "Some authors define ...") to give it more emphasis. Another possibility could be to merge the articles Noncontracting grammar and Context-sensitive grammar. Hopcroft+Ullman define (on p.223-224) a CSG as wikipedia does in Noncontracting grammar, mentioning in their next sentence that the definition at Context-sensitive grammar#Formal definition is a normal form for them, and leaving the proof as excercise 9.9 (p.230); I think that is a reasonable treatment of the issue.
I would like to discuss about the example issues, but I didn't understand which example you found to contradict to which other one. You didn't mean Noncontracting grammar#Example (which is simpler, but not context-sensitive in the wikipedia sense) vs. Context-sensitive grammar#Examples, did you? Jochen Burghardt ( talk) 09:22, 16 August 2014 (UTC)
The so-called [8] left-context and right-context grammars, which have rules on the form -> (and the dual) are [weakly-only I assume] equivalent to CSG. I do have wonder if you use "forced swaps" like -> what do you get. Probably the same thing. JMP EAX ( talk) 00:42, 16 August 2014 (UTC)
On a slightly different tack, It would be interesting to find and add historical info about: when (1) Chomsky defined his CSG, (2) who[ever] gave the non-contracting def, (3) equivalence to LBA was proven. JMP EAX ( talk) 11:44, 16 August 2014 (UTC)
The Chomsky hierarchy was defined in Chomsky (1956, [1] 1959). [2] (...) Kuroda (1964) [3] showed the equivalence of LBA's and CSG's. Previously, Myhill (1960) [4] had defined deterministic LBA's, and Landweber (1963) [5] showed that deterministic LBA languages are contained in the CSL's. Chomsky (1959) showed that the r.e. sets are equivalent to the languages generated by type-0 grammars. (...)
{{
cite journal}}
: Cite has empty unknown parameter: |month=
(
help)
{{
cite journal}}
: Cite has empty unknown parameter: |month=
(
help)
{{
cite journal}}
: Unknown parameter |month=
ignored (
help)
{{
cite report}}
: Cite has empty unknown parameter: |month=
(
help)
{{
cite book}}
: Cite has empty unknown parameter: |month=
(
help)
I'm not really sure what to do about that; there's more at context-sensitive language, but the two pages evolved independently so they aren't really a super-set of each other. But except for the normal forms, I'm not sure there are really any properties that are of CSGs per se but don't belong to the CSL page (too). JMP EAX ( talk) 13:20, 16 August 2014 (UTC)
Maybe I'm missing something again, but it seems to me that the "Kuroda normal form" is not really a normal form for CSG as defined by Chomsky. The first rule AB → CD doesn't seem to fit the CSG template of expanding a single non-terminal. JMP EAX ( talk) 13:24, 16 August 2014 (UTC)
Also there's "Kuroda normal form" for unrestricted grammars as well [12]. JMP EAX ( talk) 13:32, 16 August 2014 (UTC)
3.
It would be context-free if c would be a non-terminal, isn't it? -- Harp ( talk) 09:57, 8 October 2014 (UTC)
Hello fellow Wikipedians,
I have just modified one external link on Context-sensitive grammar. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{
Sourcecheck}}
).
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 18 January 2022).
Cheers.— InternetArchiveBot ( Report bug) 18:05, 11 September 2016 (UTC)
Is the 1774 COBOL programming language context sensitive?
It seams the divisions each having specific syntax would make it contaxt sensitive.
In the data division you can have picture defined variables having pictures clauses like:
999.99
that defines a five digit numeric field having two decmal places. The same string in the procedure division would be a numeric constant. Other picture string would not even valid in orher divisions. Basicly each COBOL division has its own syntax. This I think makes it context sensitive in the Chomsky hierarchy.
The ENVIRONMENT division was just comments, skiped by the compilers of the day.
So having different syntax bounded by constant division name strings, i.e. terminal symbols, seams to be make a context.
I haven't studied formal linguistics. Except for reading a pdf on Chomsky's grammars I found on the web. I worked on a COBOL 74 compiler in the late 1970s. Its syntax was defined by an analytical grammar/programming language.
Steamerandy ( talk) 21:37, 21 August 2018 (UTC)
Using the grammar in section Context-sensitive_grammar#k_repetitions_of_a_string, what about the following derivation:
Did I overlook some restriction in the grammar that forbids this derivation? - Jochen Burghardt ( talk) 08:10, 2 February 2022 (UTC)
(No reply for almost 2 weeks; moving dubious section to here, see below) - Jochen Burghardt ( talk) 17:41, 13 February 2022 (UTC)
=== k repetitions of a string ===
The following context-sensitive grammar with start symbol S generates :
1. |
2. |
3. |
4. |
5. |
6. |
7. "" using rules , where , |
8. "" using rules , where |
9. , where |
10. , where |
Because rule 7 can only switch two non-terminating symbols if the index of the non-terminating symbol on the left is larger, we know that non-terminals with the same index cannot be switched around, thus malforming the generated string. If, however, the rules 9 or 10 are used prematurely, the transformation to string of terminal symbols will be impossible, either because index of the leftmost non-terminal will be too high to use rule 8, or because it will be transformed into terminal symbol with other non-terminal symbols remaining. Therefore this grammar does indeed generate only the language . dubious
This grammar can also be with little effort extended to generate empty string (by adding new start symbol, that can produce either empty string or current start symbol), to generate more copies of , or to work with larger alphabet. A generation chain for abcabcabc is:
This is the
talk page for discussing improvements to the
Context-sensitive grammar article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||||||||||
|
(Contrary to a previous version of this article, the decision problem is not undecidable.)
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.
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.
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).
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 :)
There is a more standard definition of context sensitive rules (used in most textbooks): a rule x -> y is context sensitive iff |x| <= |y|.
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)
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.
Again the derivation for "aaa bbb ccc" is:
-- Gerel ( talk) 15:20, 19 December 2008 (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:
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.
(Or am I missing something?)
It seems however that the following grammar works:
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)
Using a grammar that contradicts the definition is highly confusing. What is a monotonic grammar?
HERE IS THE EASY ANSWER:
S → aSBC | abc
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc
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).
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)
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.
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:
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 [1] [2] 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, , R, S) where V is a finite set of symbols, is the subset of V which contains only the terminal symbols and S is the start symbol in V, V.
R is a finite set of production rules in the form such that and are members of V and and || || where |x| is the length of x. [3]
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)
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)
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)
There is a problem with the grammar listed on the site as of now. As I'm a new user, I'm reluctant to edit the page without the consensus of the group.
This leads to problems like:
There is no available non-terminal to fix this; it looks like this could be fixed with the additional rule:
If there is agreement here, I'll happily edit the page. Pmeixner ( talk) 22:19, 7 August 2014 (UTC)
I just noticed too that the example contradicts the one given (from a reliable source) in Noncontracting grammar which doesn't have the extra non-terminals and rules. I don't have time right now to figure it all out, but I don't see anything wrong with simpler grammar right now. JMP EAX ( talk) 00:05, 16 August 2014 (UTC)
It seems that the distinction between Context-sensitive grammar and Noncontracting grammar is a source of confusion for many readers. Probably, many authors use the name "context-sensitive grammar" for what wikipedia calls a "noncontracting grammar"; the sentence "Some definitions of a context-sensitive grammar only require that for any production rule of the form u → v, the length of u shall be less than or equal to the length of v." in Context-sensitive grammar#Formal definition tries to make that clear, but it might be necessary to rephrase it (e.g. to "Some authors define ...") to give it more emphasis. Another possibility could be to merge the articles Noncontracting grammar and Context-sensitive grammar. Hopcroft+Ullman define (on p.223-224) a CSG as wikipedia does in Noncontracting grammar, mentioning in their next sentence that the definition at Context-sensitive grammar#Formal definition is a normal form for them, and leaving the proof as excercise 9.9 (p.230); I think that is a reasonable treatment of the issue.
I would like to discuss about the example issues, but I didn't understand which example you found to contradict to which other one. You didn't mean Noncontracting grammar#Example (which is simpler, but not context-sensitive in the wikipedia sense) vs. Context-sensitive grammar#Examples, did you? Jochen Burghardt ( talk) 09:22, 16 August 2014 (UTC)
The so-called [8] left-context and right-context grammars, which have rules on the form -> (and the dual) are [weakly-only I assume] equivalent to CSG. I do have wonder if you use "forced swaps" like -> what do you get. Probably the same thing. JMP EAX ( talk) 00:42, 16 August 2014 (UTC)
On a slightly different tack, It would be interesting to find and add historical info about: when (1) Chomsky defined his CSG, (2) who[ever] gave the non-contracting def, (3) equivalence to LBA was proven. JMP EAX ( talk) 11:44, 16 August 2014 (UTC)
The Chomsky hierarchy was defined in Chomsky (1956, [1] 1959). [2] (...) Kuroda (1964) [3] showed the equivalence of LBA's and CSG's. Previously, Myhill (1960) [4] had defined deterministic LBA's, and Landweber (1963) [5] showed that deterministic LBA languages are contained in the CSL's. Chomsky (1959) showed that the r.e. sets are equivalent to the languages generated by type-0 grammars. (...)
{{
cite journal}}
: Cite has empty unknown parameter: |month=
(
help)
{{
cite journal}}
: Cite has empty unknown parameter: |month=
(
help)
{{
cite journal}}
: Unknown parameter |month=
ignored (
help)
{{
cite report}}
: Cite has empty unknown parameter: |month=
(
help)
{{
cite book}}
: Cite has empty unknown parameter: |month=
(
help)
I'm not really sure what to do about that; there's more at context-sensitive language, but the two pages evolved independently so they aren't really a super-set of each other. But except for the normal forms, I'm not sure there are really any properties that are of CSGs per se but don't belong to the CSL page (too). JMP EAX ( talk) 13:20, 16 August 2014 (UTC)
Maybe I'm missing something again, but it seems to me that the "Kuroda normal form" is not really a normal form for CSG as defined by Chomsky. The first rule AB → CD doesn't seem to fit the CSG template of expanding a single non-terminal. JMP EAX ( talk) 13:24, 16 August 2014 (UTC)
Also there's "Kuroda normal form" for unrestricted grammars as well [12]. JMP EAX ( talk) 13:32, 16 August 2014 (UTC)
3.
It would be context-free if c would be a non-terminal, isn't it? -- Harp ( talk) 09:57, 8 October 2014 (UTC)
Hello fellow Wikipedians,
I have just modified one external link on Context-sensitive grammar. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{
Sourcecheck}}
).
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 18 January 2022).
Cheers.— InternetArchiveBot ( Report bug) 18:05, 11 September 2016 (UTC)
Is the 1774 COBOL programming language context sensitive?
It seams the divisions each having specific syntax would make it contaxt sensitive.
In the data division you can have picture defined variables having pictures clauses like:
999.99
that defines a five digit numeric field having two decmal places. The same string in the procedure division would be a numeric constant. Other picture string would not even valid in orher divisions. Basicly each COBOL division has its own syntax. This I think makes it context sensitive in the Chomsky hierarchy.
The ENVIRONMENT division was just comments, skiped by the compilers of the day.
So having different syntax bounded by constant division name strings, i.e. terminal symbols, seams to be make a context.
I haven't studied formal linguistics. Except for reading a pdf on Chomsky's grammars I found on the web. I worked on a COBOL 74 compiler in the late 1970s. Its syntax was defined by an analytical grammar/programming language.
Steamerandy ( talk) 21:37, 21 August 2018 (UTC)
Using the grammar in section Context-sensitive_grammar#k_repetitions_of_a_string, what about the following derivation:
Did I overlook some restriction in the grammar that forbids this derivation? - Jochen Burghardt ( talk) 08:10, 2 February 2022 (UTC)
(No reply for almost 2 weeks; moving dubious section to here, see below) - Jochen Burghardt ( talk) 17:41, 13 February 2022 (UTC)
=== k repetitions of a string ===
The following context-sensitive grammar with start symbol S generates :
1. |
2. |
3. |
4. |
5. |
6. |
7. "" using rules , where , |
8. "" using rules , where |
9. , where |
10. , where |
Because rule 7 can only switch two non-terminating symbols if the index of the non-terminating symbol on the left is larger, we know that non-terminals with the same index cannot be switched around, thus malforming the generated string. If, however, the rules 9 or 10 are used prematurely, the transformation to string of terminal symbols will be impossible, either because index of the leftmost non-terminal will be too high to use rule 8, or because it will be transformed into terminal symbol with other non-terminal symbols remaining. Therefore this grammar does indeed generate only the language . dubious
This grammar can also be with little effort extended to generate empty string (by adding new start symbol, that can produce either empty string or current start symbol), to generate more copies of , or to work with larger alphabet. A generation chain for abcabcabc is: