sääntöjoukon

Sääntöjoukko tarkoittaa joukkoa sääntöjä, jotka määrittävät, miten tietty järjestelmässä sallitaan muunnokset tai johtopäätökset. Yleisesti sääntö on muoto LHS → RHS, jossa LHS on sovellettavan muunnoksen mallinnus (esimerkiksi osa lausetta, termi tai kaava) ja RHS on sen muunnos tai seuraava esiintymä. Sääntöjoukko voi sisältää sekä kontekstittomia että kontekstisidonnaisia sääntöjä, ja se voi olla deterministinen tai epädeterministinen riippuen siitä, antaako sama lähtötilanne aina saman lopputuloksen.

Kielitieteessä ja virallisissa kielissä sääntöjoukko määrittelee, miten merkkijonoja voidaan johdattaa tai muodostaa lauseiksi. Esimerkki kontekstittomasta kieliopista on tuotantosääntöjä, kuten S → NP VP, NP → Det N, VP → V NP, joiden avulla lause voidaan rakentaa pienemmistä osista. Tällaiset säännöt kuvaavat syntaksin rakenteellista rakennetta ja mahdollistavat kieliopin generoinnin.

Termirewriting-järjestelmissä sääntöjoukko antaa muunnossäännöt termien tai ilmaisujen muuntamiseksi kohti normaalimuotoa tai toivottua rakennetta. Esimerkki on f(x,y) → g(x,y), jolla kerrosten tai lausekkeiden rakennetta voidaan yksinkertaistaa tai muuntaa.

Loogisessa päättelyssä sääntöjoukko muodostaa johtamisjärjestelmän, jossa premissistä voidaan johdattaa johtopäätös sääntöjen sovelluksella (esim. Modus ponens: P and (P → Q) yield Q). Sääntöjoukkoihin liittyy usein ominaisuuksia, kuten termination (muunnosten päättyminen), confluence (resultaatin riippumattomuus sovitusjärjestyksestä) ja determinismi. Näiden avulla arvioidaan järjestelmän oikeellisuutta ja käytettävyyttä.