Bar-Hillelin ja Ogdenin lemmoista
Neulaniemi, Tuomas (2015)
2015
Tietojenkäsittelyopin maisteriopinnot - Master's Programme in Computer Science
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2015-10-14
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:uta-201511252457
https://urn.fi/URN:NBN:fi:uta-201511252457
Tiivistelmä
Tässä pro gradu -tutkielmassa tutkimme formaalien kielten teoriaa, erityisesti Bar-Hillelin ja Ogdenin lemmoja, joita kutsutaan pumppauslemmoiksi. Tutkimme lisäksi lineaarisille ja ei-lineaarisille kontekstittomille kielille tarkoitettua lemmaa. Ogdenin todistusta seuraa luontaisen moniselitteisyyden käsittely. Tutkimme vaihtolemmaa ja Parikhin lausetta, joita seuraa vahvojen iterointilemmojen esittely. Lopuksi katsastamme lyhyesti lemmojen tietojenkäsittelytieteellisiä sovelluksia.