“Useless rules”的意思、由来-开放百科全书

词条

Useless rules

释义

Definition
Examples
Cleaning Useless Rules
References

In theoretical computer science, in particular in the theory of formal languages, useless rules of a formal grammar are those rules of symbol production that are unreachable or unproductive, that is, that can or need never be applied. Simply, they "can be removed from the grammar without affecting the language produced"^[1]

Definition

Given a context-free grammar, a nonterminal symbol X is called productive, or generating, if there is a derivation X ⇒^* w for some string w of terminal symbols. A nonterminal symbol X is called reachable if there is a derivation S ⇒^* αXβ for some strings α, β of non-terminal and terminal symbols, and where S denotes the grammar's start symbol.

A rule with an unproductive or unreachable symbol on its left-hand side can be deleted from the grammar without changing the accepted (a.k.a. generated) language.

Likewise, an alternative containing such a symbol can be deleted from the right-hand side of a rule without changing the language.

Such rules and alternatives are called useless.^[2]

For formal grammars that are not context-free, similar definitions apply.{{citation needed|date=March 2014}}

Examples

Denoting nonterminal and terminal symbols by upper- and lower-case letters, respectively,

in the following regular grammar with start symbol S

S → Bb | Cc | Ee

B → Bb | b

C → Cc | c

D → Bd | Cd | d

E → Ee

the nonterminal D is unreachable, and E is unproductive.

Hence, omitting the last two rules doesn't change the language accepted by the grammar, nor does omitting the alternative "| Ee" from the right-hand side of the rule for S.

Cleaning Useless Rules

Hopcroft, et al.^[3] give an algorithm to eliminate useless rules from a context-free grammar.

Aiken and Murphy^[4] give a fixpoint algorithm to detect which nonterminals of a given regular tree grammar are unproductive.

References

1. ^{{Cite web|url=https://www.springer.com/cda/content/document/cda_downloaddocument/9780387202488-c1.pdf?SGWID=0-0-45-466216-p52091986|title=|last=|first=|date=|website=|archive-url=|archive-date=|dead-url=|access-date=}}
2. ^{{cite book|author1=John E. Hopcroft |author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation| year=2003| publisher=Addison Wesley}}; here: Sect.7.1.1, p.256
3. ^Theorem 7.2, Sect.7.1, p.255ff
4. ^{{cite conference|first1=A.|last1=Aiken|first2=B.|last2=Murphy|title=Implementing Regular Tree Expressions|booktitle=ACM Conference on Functional Programming Languages and Computer Architecture|pages=427–447|year=1991|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3766}}; here: Sect.4

2 : Formal languages|Rules

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。