Converting Binary Automata to Unary Automata

If is a binary language, then its unary coded version = is a unary language such that aˣ~is in~\ if and only if there exists a binary representation of~x in~\@. (Because of leading zeros, we may have more than one such binary string\@.) Conversely, the binary coded version = of a unary~\ is a binary language \ such that =, containing all binary strings representing any aˣ∈\@. We shall present a procedure that, for any given minimal binary ~, decides whether there exists a unary \ \ such that ()= ()\@. The decision itself is done in time that is polynomial in the number of states of~\@. If such \ does exist (this is not always granted), it is produced in time that is polynomial in the number of states of~\@. The gap (in terms of the number of states) between the binary \ and their unary counterparts may be exponential. Next, we shall show that the problem of whether there exists a unary \ \ such that ()= () is decidable as well. This is not always equivalent to ()= (), because of leading zeros.