Avaa päävalikko

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.

EsimerkkiMuokkaa

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.