3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Luke Mathieson Dec 30 '19 at 0:22
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 30 '19 at 18:24
  • $\begingroup$ 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? $\endgroup$ – D.W. Dec 30 '19 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.