Talk:Context-sensitive grammar
From Wikipedia, the free encyclopedia
 |
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. | ||||||||||||
|
|||||||||||||
(Contrary to a previous version of this article, the decision problem is not undecidable.)
Contents |
[edit] 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).
[edit] 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)
[edit] 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)
[edit] 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).
