Automatic Sequences

Finite automaton is a well known and utilized computational model. Automatic sequences’ definition is bootstraped using the notion of finite automaton. More specifically for the definition we use DFA (Deterministic Finite Automaton) with an output function τ and call it DFAO (Deterministic Finite Automaton with Output). Looking from the Chomsky’s hierarchy of languages it’s exactly the regular type ones that the DFA model recognizes. Using the notion of finite automaton we can show properties such as cross product of automatic sequences and composition of output functions. Relation between morphisms and finite automaton is established for automaticity of a sequence. Using morphisms we can have an alternative way of treating the automatic sequences. Additionally the notion of k−Kernels is introduced and the relation is established with automatic sequences. The interest of finding the algebraicity of formal power series will lead to Christol’s theorem which establishes the relation with automatic sequences, proving another way of representing automatic sequences by the means of formal power series, a notion from the broad field of algebra.