Yhteydetön kieli

Kohteesta Wikipedia
Siirry navigaatioon Siirry hakuun

Yhteydetön eli kontekstiton kieli on formaali kieli, jonka tunnistaa jokin pinoautomaatti. Yhteydettömän kielen tuottaa jokin yhteydetön kielioppi.

Yhteydettömillä kielillä on paljon sovelluksia ohjelmointikielissä; esimerkiksi useimmat aritmeettiset lausekkeet voidaan tuottaa yhteydettömillä kieliopeilla.

Esimerkki[muokkaa | muokkaa wikitekstiä]

Esimerkki yhteydettömästä kielestä on eli kieli, joka sisältää kaikki sellaiset merkkijonot, joissa on ensin tietty määrä merkkejä a ja sen jälkeen saman verran merkkejä b. L:n tuottaa kielioppi , ja sen hyväksyy pinoautomaatti jossa on määritelty seuraavasti::





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.
Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.