Talk:Noncontracting grammar

This is the talk page for discussing improvements to the Noncontracting grammar article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

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:

Computer science

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

??? This article has not yet received a rating on the project's importance scale.

This article has been automatically rated by a bot or other tool because one or more other projects use this class. Please ensure the assessment is correct before removing the |auto= parameter.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Philosophy: Logic Low‑importance

This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.PhilosophyWikipedia:WikiProject PhilosophyTemplate:WikiProject PhilosophyPhilosophy articles

Low

This article has been rated as Low-importance on the project's importance scale.

Associated task forces:
/
	Logic

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)[reply]

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

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)[reply]

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)[reply]

K

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]