Converting Binary Automata to Unary Automata
Geffert, Viliam · Journal of automata, languages and combinatorics · 2025
If $\cll$ is a binary language, then its \emph{unary coded version} $\cllp= um\cll$ is a unary language such that $a^{x}$~is in~\cllp\ if and only if there exists a binary representation of~$x$ in~\cll\@. (Because of leading zeros, we may have more than one such binary string\@.) Conversely, the \emph{binary coded version} $\cll= \bin\cllp$ of a unary~\cllp\ is a binary language \cll\ such that $ um\cll= \cllp$\krn, containing all binary strings representing any $a^{x}\in \cllp$\krn\@. We shall present a procedure that, for any given minimal binary \dfa~\cla, decides whether there exists a unary \dfa\ \cclap\ such that $\bin\cll(\cclap)= \cll(\cla)$\@. The decision itself is done in time that is polynomial in the number of states of~\cla\@. If such \cclap\ does exist (this is not always granted), it is produced in time that is polynomial in the number of states of~\cclap\krn\@. The gap (in terms of the number of states) between the binary \dfas\ and their unary counterparts may be exponential. Next, we shall show that the problem of whether there exists a unary \dfa\ \cclap\ such that $\cll(\cclap)= um\cll(\cla)$ is decidable as well. This is not always equivalent to $\bin\cll(\cclap)= \cll(\cla)$, because of leading zeros.