Yhteydetön kielioppi

Wikipedia
Loikkaa: valikkoon, hakuun

Yhteydetön kielioppi tai kontekstiton kielioppi on kielitieteessä ja tietojenkäsittelytieteessä formaali kielioppi, jossa jokainen kirjoitussääntö on muotoa

V → w

missä V on välike (välisymboli) ja w päätemerkeistä (päätesymboleista) ja/tai välikkeistä koostuva merkkijono. Korvauksen voi tehdä aina riippumatta V:n kontekstista eli sitä ympäröivistä symboleista; tästä nimi yhteydetön tai kontekstiton. Formaali kieli on yhteydetön jos sen tuottaa yhteydetön kielioppi. Kielioppi on kontekstiton jos ja vain jos se voidaan tunnistaa pinoautomaatilla.

Formaali määritelmä[muokkaa | muokkaa wikitekstiä]

Yhteydetön kielioppi on nelikko G = (V\,, \Sigma\,, R\,, S\,), missä

  • V on kieliopin päätemerkkien äärellinen joukko
  • \Sigma on kieliopin välikkeiden äärellinen joukko
  • R kieliopin sääntöjen eli produktioiden (äärellinen) joukko
  • S on joukon V alkio, kieliopin välikkeisiin kuuluva lähtösymboli
  • R:n alkiot ovat muotoa
\Sigma \longrightarrow (V \cup \Sigma)^*, missä * on Kleenen tähti

Esimerkkejä[muokkaa | muokkaa wikitekstiä]

Esimerkki 1:

Yksinkertainen yhteydetön kielioppi on

S → aSb | ε

Kielioppi tuottaa kielen  \{ a^n b^n : n \ge 0 \}

Esimerkki 2:

Seuraava kielioppi tuottaa sellaisista aakkoston {a,b} merkkijonoista koostuvan kielen, joissa on eri määrä merkkejä a ja b.

S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε

Tässä T voi tuottaa kaikki merkkijonot, joissa on sama määrä a:ta ja b:tä. U tuottaa merkkijonot, joissa on enemmän a- kuin b-merkkejä ja V vastaavasti sellaiset jonot, joissa a:ta on vähemmän.

Kontekstivapaiden kielten joukon ominaisuuksia[muokkaa | muokkaa wikitekstiä]

Kontekstivapaiden kielten joukko on suljettu yhdisteen, katenaation ja Kleenen tähden suhteen, mutta toisin kuin säännöllisten kielten joukko, se ei ole suljettu leikkauksen tai komplementin suhteen.


Johdot ja jäsennyspuut[muokkaa | muokkaa wikitekstiä]

On kaksi tapaa kuvata kuinka tietty merkkijono voidaan tuottaa annetusta kieliopista. Yksinkertaisempi tapa on listata peräkkäiset symbolijonot alkaen lähtösymbolista ja päättyen lopulliseen merkkijonoon. Jos jokaisessa johdon askeleessa produktiota käytetään merkkijonon vasemmanpuoleisimpaan välikkeeseen, kyseessä on ns. vasen johto, vastaavasti voidaan määritellä oikea johto. Esimerkiksi seuraavassa kieliopissa

S → S + S | 1

merkkijonon "1 + 1 + 1" voi tuottaa vasemmalla johdolla (S → S + S → 1 + S → 1 + S + S → 1 + 1 + S → 1 + 1 + 1) tai oikealla johdolla (S → S + S → S + 1 → S + S + 1 → S + 1 + 1 → 1 + 1 + 1).

Johtoja voidaan kuvata myös jäsennyspuilla. Jäsennyspuut karsivat johdoista pois epäoleelliset erot. Esimerkiksi edellä kuvatussa vasemmassa johdossa jäsennyspuu on samanlainen, suoritettiinpa produktiot sitten järjestyksessä 1 + S + S → 1 + 1 + S → 1 + 1 + 1 tai 1 + S + S → 1 + S + 1 → 1 + 1 + 1. Seuraavassa on esitetty tämän johdon jäsennyspuu:

           S 
          /|\
         / | \
        /  |  \
       S  '+'  S
       |      /|\
       |     / | \
      '1'   S '+' S
            |     |
           '1'   '1'

Jos samalle merkkijonolle on kieliopissa mahdollista laatia useita jäsennyspuita, kieliopin sanotaan olevan moniselitteinen.

Normaalimuodot[muokkaa | muokkaa wikitekstiä]

Kukin yhteydetön kielioppi voidaan muuttaa vastaavaksi Chomskyn normaalimuodossa tai Greibachin normaalimuodossa olevaksi kieliopiksi; jälkimmäinen sillä ehdolla, ettei kielioppi tuota tyhjää merkkijonoa. "Vastaava" tarkoittaa tässä sitä, että kieliopit tuottavat saman kielen.

Chomskyn normaalimuodossa olevan kieliopin produktiot ovat erityisen yksinkertaisia, minkä vuoksi tällä normaalimuodolla on sekä teoreettisia että käytännön sovelluksia. Sen avulla voidaan esimerkiksi konstruoida algoritmi, joka ratkaisee kuuluuko annettu merkkijono kieliopin tuottamaan kieleen vai ei (CYK-algoritmi).

Katso myös[muokkaa | muokkaa wikitekstiä]

Automaattiteoria: formaalit kielet ja formaalit kieliopit
Chomskyn
hierarkia
Kielioppi Kieli Tunnistusautomaatti
luokka 0 Rajoittamaton Rekursiivisesti numeroituva Turingin kone
Rajoittamaton Rekursiivinen Totaalinen Turingin kone
luokka 1 Yhteysherkkä Yhteysherkkä Lineaarisesti rajoitettu
luokka 2 Yhteydetön Yhteydetön Pinoautomaatti
luokka 3 Säännöllinen Säännöllinen Äärellinen
Kukin luokka on sen yläpuolisen luokan aito osajoukko.