Yhteydetön kieli

Kohteesta Wikipedia
Loikkaa: valikkoon, 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.