Automaattiset jonot ja Cobhamin lause
Nuutila, Mikael (2021-08-03)
Automaattiset jonot ja Cobhamin lause
Nuutila, Mikael
(03.08.2021)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021081142911
https://urn.fi/URN:NBN:fi-fe2021081142911
Tiivistelmä
Tutkielman tarkoituksena on esitellä Thijmen J. P. Krebsin uusi aikaisempaa lyhyempi todistus k-automaattisia jonoja koskevalle Cobhamin lauseelle. Oletetaan, että k > 1 ja h > 1 ovat multiplikatiivisesti riippumattomia luonnollisia lukuja.Tällöin Cobhamin lauseen mukaan äärellisen aakkoston jono on sekä k-että h-automaattinen silloin ja vain silloin kun se on lopulta jaksollinen. Cobhamin lauseen lisäksi perehdytään joihinkin k-automaattisten jonojen perusominaisuuksiin. Tarkastellaan k-automaattisia jonoja erityisesti automaattis-teoreettiselta kannalta. Pääpaino on niissä tuloksissa joita tarvitaan Cobhamin lauseen todistuksessa.
Esitetään tarpeelliset pohjatiedot formaalisten kielten ja säännöllisten kielten teoriasta. Perehdytään myös lukujärjestelmiin, erityisesti tutkielman aiheen kannalta keskeisiin k-kantajärjestelmiin. Määritellään äärelliset funktioautomaatit, automaattiset funktiot, äärelliset transduktorit ja myy-transduktorit. Määritellään k-automaattiset jonot syöttämällä jonon indeksien k-kantaesityksiä funktioautomaatille. Osoitetaan, että lopulta jaksollinen jono on aina k-automaattinen. Muodostetaan myy-transduktori, joka laskee normalisaation kannassa k. Käytetään tätä transduktoria todistamaan, että jono on k-automaattinen silloin ja vain silloin kun se on (k,D)-automaattinen. Oletetaan, että k > 1 ja h > 1 ovat multiplikatiivisesti riippumattomia kokonaislukuja. Osoitetaan, että tällöin jono on lopulta jaksollinen, mikäli se on (k,D_k)- ja (h,D_h)-automaattinen. Cobhamin lause seuraa.
Esitetään tarpeelliset pohjatiedot formaalisten kielten ja säännöllisten kielten teoriasta. Perehdytään myös lukujärjestelmiin, erityisesti tutkielman aiheen kannalta keskeisiin k-kantajärjestelmiin. Määritellään äärelliset funktioautomaatit, automaattiset funktiot, äärelliset transduktorit ja myy-transduktorit. Määritellään k-automaattiset jonot syöttämällä jonon indeksien k-kantaesityksiä funktioautomaatille. Osoitetaan, että lopulta jaksollinen jono on aina k-automaattinen. Muodostetaan myy-transduktori, joka laskee normalisaation kannassa k. Käytetään tätä transduktoria todistamaan, että jono on k-automaattinen silloin ja vain silloin kun se on (k,D)-automaattinen. Oletetaan, että k > 1 ja h > 1 ovat multiplikatiivisesti riippumattomia kokonaislukuja. Osoitetaan, että tällöin jono on lopulta jaksollinen, mikäli se on (k,D_k)- ja (h,D_h)-automaattinen. Cobhamin lause seuraa.