Useless regels - Useless rules

In de theoretische informatica , in het bijzonder in de theorie van formele talen , nutteloze regels van een formele grammatica zijn de regels van het symbool productie die onbereikbaar of onproductief zijn, dat wil zeggen, dat kan of hoeft nooit worden toegepast.

Definitie

Bij een context-vrije grammatica een eindstandige symbool X heet productieve of genereren , als er een afleiding X ⇒ * w enkele reeks w van terminalsymbolen. Een eindstandige symbool X heet bereikbaar als er een afleiding S ⇒ * α X β enige strings α, β van eindstandige en terminalsymbolen en waarbij S staat voor de grammatica startsymbool .

Een regel met een onproductieve of onbereikbaar is, staat op de linkerzijde kan worden verwijderd uit de grammatica zonder wijziging van de aanvaarde (aka gegenereerd) taal. Evenzo kan een alternatief die een dergelijk symbool verwijderd uit de rechterkant van een regel zonder de taal. Deze regels en alternatieven worden genoemd nutteloos .

Voor formele grammatica die niet context-vrij , soortgelijke definities van toepassing.

Voorbeelden

Duidt eindstandige en terminalsymbolen met hoofdletters en kleine letters, respectievelijk in de volgende reguliere grammatica met startsymbool S

S → Bb | cc | ee
B → Bb | b
C → Cc | c
D → Bd | cd | d
E → Ee

het eindstandige D onbereikbaar en E niet productief. Vandaar dat het weglaten van de laatste twee regels de taal die door de grammatica aanvaard te veranderen, noch het weglaten van de alternatieve "| Ee " van de rechterzijde van de regel voor S .

Reinigen Useless Regels

Hopcroft, et al. geven een algoritme om nutteloze regels uit een elimineren grammatica zonder context .

Aiken en Murphy geeft een fixpoint algoritme om te detecteren welke nonterminals van een bepaalde regelmatige boom grammatica zijn onproductief.

Referenties