Yhteydetön kieli

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älähde?; esimerkiksi useimmat aritmeettiset lausekkeet voidaan tuottaa yhteydettömillä kieliopeilla.

Esimerkki

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::





Lähteet

  • Ruzzo, Walter Lawrence: General context-free language recognition. Väitöskirja : University of California. Ann Arbor (Mich.): UMI, 1978. (englanniksi)
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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.