On extension of stochastic k -automata

Abstract

There are a great many research works concerning the well-known stochastic automata of Moore, Mealy, Rabin, Turing and others. Recently an automaton of Markov’s chain type has been introduced by Bartoszyński. This automaton is obtained by a generalization of Pawlak’s deterministic machine.

The aim of this note is to give a concept of a stochastic automaton of Markov’s generalized chain type. The introduced automaton called a stochastic k-automaton (s.k-a.) is a common generalization of Bartoszyński’s automaton and Grodzki’s deterministic k-machine.

By a stochastic k-automaton we mean an ordered triple ${\mathit{M}}_{\mathit{k}}=⟨\mathit{U}\mathrm{,}\mathit{a}\mathrm{,}\mathit{\pi }⟩$ , $\mathit{k}⩾1$ , where U denotes a finite non-empty set, a is a function from U ^k to [0, 1] with ${\sum }_{\mathit{v}\in {\mathit{U}}^{\mathit{k}}}\mathit{a}\mathrm{(}\mathit{v}\mathrm{)}=1$ , and π is a function from U ^k+1 to [0,1] with ${\sum }_{\mathit{u}\in \mathit{U}}\mathit{\pi }\mathrm{(}\mathit{v}\mathrm{,}\mathit{u}\mathrm{)}=1$ for every $\mathit{v}\in {\mathit{U}}^{\mathit{k}}$ .

For all $\mathit{N}⩾\mathit{k}$ we can define a probability measure P _N on ${\mathit{U}}^{\mathit{N}}=\mathit{U}\times \mathit{U}\times \dots \times \mathit{U}$ as follows: ${\mathit{P}}_{\mathit{N}}\mathrm{(}{\mathit{u}}_1\mathrm{,}{\mathit{u}}_2\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{N}}\mathrm{)}=\mathit{a}\mathrm{(}{\mathit{u}}_1\mathrm{,}{\mathit{u}}_2\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{k}}\mathrm{)}\mathit{\pi }\mathrm{(}{\mathit{u}}_1\mathrm{,}{\mathit{u}}_2\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{k}+1}\mathrm{)}\mathit{\pi }\mathrm{(}{\mathit{u}}_2\mathrm{,}{\mathit{u}}_3\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{k}+2}\mathrm{)}\dots \mathit{\pi }\mathrm{(}{\mathit{u}}_{\mathit{N}-\mathit{k}}\mathrm{,}{\mathit{u}}_{\mathit{N}-\mathit{k}+1}\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{N}}\mathrm{)}$ .

We deal with the problems of the shrinkage and the extension of a system of s.k-a.’s ${\mathit{M}}_{\mathit{k}}^{\mathrm{(}\mathit{i}\mathrm{)}}=⟨\mathit{U}\mathrm{,}{\mathit{a}}^{\mathrm{(}\mathit{i}\mathrm{)}}\mathrm{,}{\mathit{\pi }}^{\mathrm{(}\mathit{i}\mathrm{)}}⟩$ , $\mathit{i}=1\mathrm{,}2\mathrm{,}\dots \mathrm{,}\mathit{m}\mathrm{,}\mathit{m}⩾2$ . In this note there are given conditions under which an s.k-a. ${\mathit{M}}_{\mathit{k}}=⟨\mathit{U}\mathrm{,}\mathit{a}\mathrm{,}\mathit{\pi }⟩$ exists and the language of this automaton defined as ${\mathit{L}}_{\mathit{M}}=\{\mathrm{(}{\mathit{u}}_1\mathrm{,}{\mathit{u}}_2\mathrm{,}{\mathit{u}}_3\mathrm{,}\dots \mathrm{)}:{\wedge }_{\mathit{N}⩾1}{\mathit{P}}_{\mathit{N}}\mathrm{(}{\mathit{u}}_{\mathit{l}}\mathrm{,}{\mathit{u}}_2\mathrm{,}\dots {\mathit{u}}_{\mathit{N}}\mathrm{)}\mathrm{>}0\}$ either contains the languages of all the automata ${\mathit{M}}_{\mathit{k}}^{\mathrm{(}\mathit{i}\mathrm{)}}\mathrm{,}\mathit{i}=1\mathrm{,}2\mathrm{,}\dots \mathrm{,}\mathit{m}$ , or this language equals the intersection of all those languages.