ℒ⊆{0,1}∗ is a binary coded unary regular language, if there exists a unary regular language ℒ′⊆{a}∗ such that ax is in ℒ′ if and only if the binary representation of x is in ℒ. If a unary language ℒ′ is accepted by a minimal deterministic finite automaton (DFA) 𝒜′ with n states, then its binary coded version ℒ is regular and can be accepted by a DFA 𝒜 using at most n states, but at least 1+⌈logn⌉ states. There are witness languages matching these upper and lower bounds exactly, for each n.
More precisely, if 𝒜′ uses σ≥0 states in the initial segment and μ⋅2ℓ states in the loop, where μ is odd and ℓ≥0, then the minimal 𝒜 for ℒ consists of a preamble with at most σ but at least max{1,1+⌈logσ⌉−ℓ} states, except for σ=0 with no preamble, and a kernel with at most μ⋅2ℓ but at least μ+ℓ states. Also these lower bounds are matched exactly by witness languages, for each σ,μ,ℓ. If the length of the loop is fixed, the size of the preamble is bounded by O(σ/logσ).
The conversion in the opposite way is not always granted: there are binary regular languages the unary versions of which are not even context free.
The conversion of a unary nondeterministic finite automaton (NFA) to a binary NFA uses O(n2) states and introduces a binary version of Chrobak normal form.