Talk:Noncontracting grammar

S -> empty

According to the article, a grammar is essentially noncontracting if it contains the production $S\to \varepsilon$. But if S is allowed to occur in any right-hand side, that would mean that the essentially noncontracting grammars generate the rec. enumerable languages! Should In that case, S may not occur in the right-hand side of any production. be added? -- UKoch (talk) 14:45, 22 March 2013 (UTC)

Definitely. Fixed. Rp (talk) 09:00, 14 October 2013 (UTC)

What sort of citation needed?

On the need for citation: what sort of citation is good enough? This is easy and it's in many textbooks, e.g. this one. Rp (talk) 09:00, 14 October 2013 (UTC)

It would be nice to at least have citations for the properties discussed in the final section. QVVERTYVS (hm?) 09:11, 14 October 2013 (UTC)

K

Kuroda normal form also exists for unrestricted grammars. See ref I added in there. JMP EAX (talk) 15:29, 16 August 2014 (UTC)

Q

By the way, who discovered these noncontracting grammars and their [weak] equivalence to [Chomsky's 1959] CSG def? JMP EAX (talk) 15:38, 16 August 2014 (UTC)

According to Levelt, it was most likely also Chomsky. Levelt says that Chomsky first published his CSG def in

• Chomsky, N. 1959a. On certain formal properties of grammars. Information and Control 2: 137–67.

and then published the equivalence with non-contracting grammar in:

• Chomsky, N. 1963. Formal properties of grammar. Handbook of Mathematical Psychology. R.D. Luce, R.R. Bush, & E. Galanter (eds), New York: Wiley.

It's still possible, but unlikely that someone else actually introduced the concept of non-contracting grammar sometime in between these. JMP EAX (talk) 20:58, 16 August 2014 (UTC)

After I checked out that 1963 source, he does define them, but calls them "type 1 grammar" on p. 360. JMP EAX (talk) 21:28, 16 August 2014 (UTC)

Merge?

I just spent some time trying to make this article easier to understand. More can be done; for instance, I'm not sure if the explicit conversion procedure to context-sensitive form adds all that much.

One major obstacle remains: noncontracting grammars are not the same thing as context-sensitive grammars in the Chomsky sense, but they are so closely related that the term context-sensitive grammars is applied to both, and their articles are bound to contain a lot of duplication, or worse, inconsistencies (such as in treatment of the empty string).

I think the only good way to resolve this is to merge them. It would be even better to also fold in Kuroda normal form. Doing this will make it easier for editors to stick to one consistent storyline and terminology.

What do you think? Rp (talk) 19:27, 25 May 2023 (UTC)