Binary Coded Unary Regular Languages.

ℒ⊆{0, 1}∗ is a <italic>binary coded unary regular language</italic>, 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 + ⌈log n⌉ 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. [ABSTRACT FROM AUTHOR]