Automaattiset jonot ja Cobhamin lause

Abstract

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.