Talk:Useless rules

This redirect 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 redirect has been rated as Low-importance on the project's importance scale.

Associated task forces:
/
	Logic

Proposed merge[edit]

This article should be merge into Context-free grammar, with a redirect. This would (1) solve the "missing context" issue here, and (2) provide the lacking definitions of "productive", "reachable", "useless", etc. in Context-free grammar. And of course it would avoid duplication of contents. - Jochen Burghardt (talk) 10:25, 6 February 2019 (UTC)[reply]

@Jochen Burghardt: Are you sure about the target? I think the definition here makes perfect sense beyond the context-free setting, and the article contains mention of regular tree grammars as well. Also the article Context-free grammar is quite long as it is. (On the other hand I'm skeptical that this topic really stands on its own, so I am sympathetic to the idea of merging it somewhere.) --JBL (talk) 14:09, 16 May 2020 (UTC)[reply]

@Joel B. Lewis: As far as I know, the notion of useless rules exists only for context-free grammars and subclasses thereof. The sentence claiming the contrary has an open {{citation needed}} since 2014. (Regular tree grammars are such a subclass when considered as generating/accepting strings rather than trees.) This, together with my preference for avoiding repetitions (inspired by a software engineering policy), was my motivation to suggest the merge.

You are right that the article Context-free grammar is rather long. I just thought of a merge into Chomsky normal form instead, but then had to recognize that Chomsky doesn't require absence of useless rules (Hopcroft.Ullman.1979 don't state absence of useless rules in the Chomsky-normal-form theorem, but in their proof they apply useless-rule-elimination nevertheless). On the other hand, Useless rules is quite short, and overlaps with Context-free grammar#Reachability, productiveness, nullability, so the length growth by a merge into the latter would be minimal. - Jochen Burghardt (talk) 17:47, 16 May 2020 (UTC)[reply]

@Jochen Burghardt: Ok, fair enough, you have convinced me :). I think if you want to do the merge, you should go ahead; if you don't, perhaps I will get to it some time this week. --JBL (talk) 18:06, 16 May 2020 (UTC)[reply]

Done I made a first suggestion how the merge outcome could look like at Context-free_grammar#Reachability,_productiveness,_nullability. When looking for which notation to use, I found that in section Context-free_grammar#Proper_CFGs much of the stuff is repeated. I intend to fix this lateron; the article Useless rules should be kept in its present form until everything is settled. - By the way: the main reason for the article length appears to be the presence of many, and mastly badly formatted, examples (also in Section "Derivations and syntax trees"), not all of which are helpful. - Jochen Burghardt (talk) 07:34, 17 May 2020 (UTC)[reply]

@Jochen Burghardt: It looks good. Indeed, duplication: I had seen the section on proper CFGs but not the section on reachability, etc.! I will convert this article into a redirect in a moment. --JBL (talk) 16:59, 18 May 2020 (UTC)[reply]