Automaattiset jonot ja Cobhamin lause
397.33 KB
avoin
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Lataukset269
Pysyvä osoite
Verkkojulkaisu
DOI
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.