Kontekstivapaa

Kontekstivapaa, englanniksi context-free, on käsite muodollisissa kielissä ja kieliopissa. Se kuvaa kieliopin, jossa säännöt ovat muotoa A → α, missä A on yksi ei-termiaali ja α on merkkijono, joka koostuu lopputerminaaleista ja/tai ei-termiaaleista. Näin säännön sovellus ei riipu ympäröivästä kontekstista; muuttuja voidaan korvata samalla tavalla missä tahansa sen esiintymässä. Kieli on kontekstivapaa, jos sen syntaksi voidaan tuottaa tällaisesta kontekstivapaa-grammattiasta G = (V, Σ, R, S).

Kontekstivapaat kielet ovat keskeinen luokka Chomsky-hierarkiassa. Ne sisältävät säännölliset kielet ja ne muodostavat suuremman ja monimutkaisemman joukon. Esimerkki kontekstivapaasta kielestä on tasapainotettujen sulkujen kieli: S → SS | (S) | ε.

Käytännössä kontekstivapaat kielet ovat tärkeitä ohjelmointikielten syntaksin määrittämisessä. Niitä voidaan tunnistaa pushdown-automaatin avulla, ja parsinnassa hyödynnetään usein CYK- tai Earley-tyyppisiä algoritmeja. CF-kielet ovat suljettuja yhteenlaskun, konkatenaation ja Kleene-starin suhteen, mutta eivät ole suljettuja monien muiden operaatioiden, kuten komplementin tai toistensa kanssa kappaleiden osalta.

Kontekstivapaa termi ei tarkoita, että kieli olisi yksinkertainen: luonnollinen kieli voi vaatia kontekstisidonnaisia rakenteita, joita kontekstivapaa formaali ei aina riitä kuvaamaan.

Lisätietoja: Chomsky-hierarkia, kontekstisidonnaiset kielet, parsintateoriat.