Automaattiteoriaa äärettömillä sanoilla
Selin, Matias (2024)
Selin, Matias
2024
Matematiikan ja tilastotieteen kandidaattiohjelma - Bachelor's Programme in Mathematics and Statistics
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ä
2024-04-19
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202404163609
https://urn.fi/URN:NBN:fi:tuni-202404163609
Tiivistelmä
Matematiikassa automaattiteoria tutkii automaateiksi kutsuttuja abstrakteja koneita, jotka lukevat merkkijonoja eli sanoja ja joko hyväksyvät tai hylkäävät ne tiettyjen sääntöjen perusteella. Tässä tutkielmassa tarkastellaan erityisesti syötesanojen pituuden äärellisyyden ja äärettömyyden vaikutusta erilaisten automaattiluokkien kykyyn tunnistaa eli hyväksyä täsmälleen tietynlaisia sanojen joukkoja eli kieliä.
Tutkielmassa esitetään ensin luvussa 2 formaalien kielten ja sanojen keskeisiä määritelmiä sekä äärellisiä sanoja lukevat äärelliset automaatit. Luvussa 3 taas tarkastellaan Büchin automaatteja, eli erästä äärellisten automaattien yleistystä äärettömille sanoille. Lukujen päätuloksina osoitetaan näiden eri automaattiluokkien tunnistamien kielten samankaltaisuus säännöllisyyden käsitteen avulla, sekä vertaillaan automaattien laskennan deterministisyyden vaikutusta niiden tunnistusvoimaan.
Tutkielman lopussa luvussa 4 tarkastellaan hajautettuja automaatteja ja niiden tietyn rajoitetun alaluokan eli unohtavien hajautettujen automaattien vastaavuutta äärellisten automaattien ja Büchin automaattien kanssa. Uutena tuloksena osoitetaan, että unohtavat hajautetut automaatit voivat tunnistaa kaikki determinististen Büchin automaattien tunnistamat kielet.
Tutkielmassa esitetään ensin luvussa 2 formaalien kielten ja sanojen keskeisiä määritelmiä sekä äärellisiä sanoja lukevat äärelliset automaatit. Luvussa 3 taas tarkastellaan Büchin automaatteja, eli erästä äärellisten automaattien yleistystä äärettömille sanoille. Lukujen päätuloksina osoitetaan näiden eri automaattiluokkien tunnistamien kielten samankaltaisuus säännöllisyyden käsitteen avulla, sekä vertaillaan automaattien laskennan deterministisyyden vaikutusta niiden tunnistusvoimaan.
Tutkielman lopussa luvussa 4 tarkastellaan hajautettuja automaatteja ja niiden tietyn rajoitetun alaluokan eli unohtavien hajautettujen automaattien vastaavuutta äärellisten automaattien ja Büchin automaattien kanssa. Uutena tuloksena osoitetaan, että unohtavat hajautetut automaatit voivat tunnistaa kaikki determinististen Büchin automaattien tunnistamat kielet.
Kokoelmat
- Kandidaatintutkielmat [8798]