Hyödyttömät säännöt - Useless rules

Vuonna tietojenkäsittelyteoria , erityisesti teorian virallista kieltä , hyödytön sääntöjä on formaali kielioppi ovat niitä sääntöjä ja symboli tuotantovälineitä saavuttamattomissa tai tuottamatonta, eli joka voi tai tarvitse koskaan käyttää. Yksinkertaisesti, ne "voidaan poistaa kielioppia vaikuttamatta tuotettuun kieleen"

Määritelmä

Kun annetaan kontekstivapaa kielioppi , epäterminaalista symbolia X kutsutaan tuottavaksi tai generoivaksi , jos jokaiselle päätesymbolien merkkijonolle w on johdannainen X ⇒ * w . Epäterminaalista symbolia X kutsutaan saavutettavaksi, jos johdolle S ⇒ * α X β on joillekin merkkijonoille α, β ei-terminaalisille ja terminaalisymboleille, ja missä S merkitsee kieliopin alkusymbolia .

Sääntö, jonka vasemmalla puolella on tuottamaton tai tavoittamaton symboli, voidaan poistaa kielioppia muuttamatta hyväksyttyä (aka luotua) kieltä. Samoin vaihtoehto, joka sisältää tällaisen symbolin, voidaan poistaa säännön oikealta puolelta kieltä muuttamatta. Sellaisia ​​sääntöjä ja vaihtoehtoja kutsutaan turhiksi .

Muodollisille kieliopeille, jotka eivät ole kontekstivapaita , sovelletaan vastaavia määritelmiä.

esimerkit

Epäterminaalisten ja terminaalisymbolien merkitseminen isoilla ja pienillä kirjaimilla seuraavassa säännöllisessä kielioppissa aloitusmerkillä S

S → Bb | Kopio | Ee
B → Bb | b
C → Cc | C
D → Bd | CD | d
E → Ee

epäterminaalinen D on tavoittamaton, ja E on tuottamaton. Siksi kahden viimeisen säännön jättäminen ei muuta kieliopin hyväksymää kieltä eikä vaihtoehtoisen "| Ee " jättäminen S: n säännön oikealta puolelta .

Hyödyttömien sääntöjen puhdistaminen

Hopcroft, et ai. antaa algoritmi turhien sääntöjen poistamiseksi kontekstivapaasta kielioppista .

Aiken ja Murphy antavat kiinteän pisteen algoritmin havaita, mitkä tietyn säännöllisen puun kieliopin epäterminaalit eivät ole tuottavia.

Viitteet