# Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet?

Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet? Is this even a meaningful question?

For example, if $$\Sigma = \{\texttt{0}, \texttt{1}\}$$, we can encode any larger alphabet using $$\Sigma$$, but if $$\Sigma = \{\texttt{0}\}$$, this can define a DFA (that say, recognizes $$L = \{ \texttt{0}^k \mid k > 0\}$$)... but such a DFA would never be able to recognize more "complex" regular expressions. For example, there is no way to encode $$\texttt{0011}$$ using a unary alphabet that a DFA would recognize (we could use, say, Godel numbering, but that would require a more powerful machine that could "count").

If DFAs with a unary alphabet less powerful than DFAs with a binary alphabet, is there a name for this language/grammar? I recognize this is kind of an odd question, since the DFA that recognizes $$L = \{ \texttt{0}^k \mid k > 0\}$$ recognizes all unary languages... but technically there still are a countably infinite number of DFAs in this class ($$L = \{ \texttt{0}^1 \}$$, $$L=\{\texttt{0}^2\}$$, etc.)

Note I am of course assuming that for $$\Sigma = \{ \texttt{0} \}$$, that it does not contain the empty symbol $$\varepsilon$$.

• Finite automata with unary alphabets are, imaginatively, known as "Unary Finite Automata", and there seems to be a small body of ongoing reasearch. This (older) paper may give you a starting point to dig into it (though its primary aim is elsewhere). – Luke Mathieson Dec 30 '19 at 0:22

Take the set $$A=\{2^k \mid k \ge 1\}$$. The language $$L=\{ \text{bin}(a) \mid a \in A\} = \{10^k\mid k \ge 0 \}$$ is clearly a regular language, whereas $$L=\{ 1^a \mid a \in A\}$$ is not regular. Proving the latter is a standard textbook application of the regular pumping lemma.

It appears as if they are indeed less powerful.

Consider the language $$L = \{1 b (0|1)^* b \mid b \in \{0,1\}\}$$ for a binary alphabet.

The language can be recognized by a five-state DFA.

It shouldn't be too hard to show that $$L' = \{0^i \mid i \text{ is the unary encoding of some string in } L\}$$ cannot be recognized by a DFA, as the states reached for some $$0^i \neq 0^j$$ cannot be merged for $$i \neq j$$. The basic idea is that a DFA for $$L'$$ has to keep track of how many digits the word encoded by $$i$$ and $$j$$ has already to not forget the second digit. But then merging states for $$i$$ and $$j$$ would lose this information.

This is not a formal proof, but it should be a suitable starting point for a formal proof.

• Do you mean $L = (10(0|1)^*0)|(11(0|1)^*1)$? $L$ should be a set of words, not a set of regexps, so it doesn't make sense to use set notation when the left-hand-side is a regexp. – D.W. Dec 30 '19 at 18:24
• I don't understand the proof; can you expand on the proof idea a little bit more? For instance, if $i,j$ are unary encodings of two strings in $L$ of the same length, I don't understand why the states for $i,j$ can't be merged. Also I don't understand why the DFA needs to keep track of those lengths. Maybe I haven't understood the idea yet? – D.W. Dec 30 '19 at 18:28