Languages recognized by programs over the two-element monoid (Q1118041)

A program \(P_ n\) over a finite monoid M is a sequence of instructions \(v_ 1,...,v_ m\) consisting of pairs \(v_ r=(i_ r,f_ r)\), where \(f_ r\) is a function from a finite alphabet A to M and \(i_ r\) is an integer, \(1<i_ r<n\). A program yields a mapping from \(A^ n\) to M in a natural way. A language L in \(A^*\) is recognizable by programs if for every n there is a program \(P_ n\) and a subset \(F_ n\) of M such that \(L\cap A^ n=P_ n^{-1}(F_ n)\). In the present paper the recognizability of the languages in binary alphabet are studied with respect to the two element monoid.