Formaalien kielten vaativuusteoriaa ja pelillistämistä
Ahvonen, Veeti (2022)
2022
Matematiikan maisteriohjelma - Master´s Programme in Mathematics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication 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ä
2022-05-23
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202204294169
https://urn.fi/URN:NBN:fi:tuni-202204294169
Tiivistelmä
Tutkielmassa tarkastellaan säännöllisten, kontekstivapaiden ja konjunktiivisten kielten vaativuusteoriaa sekä semanttisia pelejä. Tutkielman alussa esitellään tarvittavia käsitteitä ja merkintöjä formaaleista kielistä, malliteoriasta sekä loogikoista. Tutkielma etenee tarkastellen kutakin kieliperhettä omassa kappaleessaan.
Säännöllisten kielten kappaleessa määritellään säännöllisten kielten semanttinen peli eli pelin, joka karakterisoi säännölliset kielet, ja osoitetaan pelin korrektius. Tämän jälkeen tarkastellaan säännöllisten kielten Ehrenfeucht–Fraïssé-peliä. Tunnettuun säännöllisten kielten loogiseen krakterisointiin ei tässä tutkielmassa paneuduta, vaan se oletetaan tunnetuksi.
Säännöllisten kielten jälkeen tarkastellaan kontekstivapaita kieliä. Kontekstivapaille kielille määritellään vastaava semanttinen peli, joka osoittautuu huomattavasti monimutkaisemmaksi kuin säännöllisten kielten semanttinen peli. Tämän jälkeen tarkastellaan kontekstivapaiden kielten vaativuusteoriaa ja loogista karakterisointia pinoautomaattien kautta.
Tutkielman lopussa tarkastellaan konjunktiivisten kielten semanttista peliä ja automaatioteoriaa. Tutkielmassa osoitetaan yhteys usean kulun pinoautomaatin ja yksinkertaistetun synkronoidun vuorottelevan pinoautomaatin välillä. Lisäksi annetaan looginen karakterisointi kojunktiivisten kielten aliluokalle BC+(CFL), joka on kontekstivapaiden kielten sulkeuma yhdisteen ja leikkauksen suhteen.
Säännöllisten kielten kappaleessa määritellään säännöllisten kielten semanttinen peli eli pelin, joka karakterisoi säännölliset kielet, ja osoitetaan pelin korrektius. Tämän jälkeen tarkastellaan säännöllisten kielten Ehrenfeucht–Fraïssé-peliä. Tunnettuun säännöllisten kielten loogiseen krakterisointiin ei tässä tutkielmassa paneuduta, vaan se oletetaan tunnetuksi.
Säännöllisten kielten jälkeen tarkastellaan kontekstivapaita kieliä. Kontekstivapaille kielille määritellään vastaava semanttinen peli, joka osoittautuu huomattavasti monimutkaisemmaksi kuin säännöllisten kielten semanttinen peli. Tämän jälkeen tarkastellaan kontekstivapaiden kielten vaativuusteoriaa ja loogista karakterisointia pinoautomaattien kautta.
Tutkielman lopussa tarkastellaan konjunktiivisten kielten semanttista peliä ja automaatioteoriaa. Tutkielmassa osoitetaan yhteys usean kulun pinoautomaatin ja yksinkertaistetun synkronoidun vuorottelevan pinoautomaatin välillä. Lisäksi annetaan looginen karakterisointi kojunktiivisten kielten aliluokalle BC+(CFL), joka on kontekstivapaiden kielten sulkeuma yhdisteen ja leikkauksen suhteen.