11
$\begingroup$

Question

Let $M$ be some DFA that reads integers in base $k$. Does there always exist some other DFA $M'$ that also reads integers in base $k$, where $M'(x)$ accepts if and only if $M$ accepts the majority of words less than $x$?

Background and motivation

According to the cited paper, the above process works if we replace "majority" with "modulo $p$" for some constant $p$; that is, we can build a second DFA $M'$ where $M'(x)$ accepts if and only if $M$ accepts 0 mod $p$ words less than $x$. However, this is still in some sense a very "regular" task, in the sense that DFAs can calculate the number of 1s in a string mod $p$, so I am curious to see whether it extends to a simple problem that is not "regular" in the same way.

Lecomte, P. B. A.; Rigo, M., Numeration systems on a regular language, Theory Comput. Syst. 34, No. 1, 27-44 (2001). ZBL0969.68095.

$\endgroup$
2
  • $\begingroup$ How do you manage the strings starting with 0? Presumably you don't intend the interpret the (infinitely many) strings in 0* as all less than 1? $\endgroup$
    – Neal Young
    Oct 9, 2022 at 16:22
  • $\begingroup$ @NealYoung I'm assuming that $M$ is insensitive to leading 0s. $\endgroup$
    – Jake
    Oct 9, 2022 at 19:59

1 Answer 1

2
+50
$\begingroup$

No. Consider the language $L$ of numbers whose binary representation starts with 10, except for the powers of 2. So the first few numbers in $L$ are 101, 1001, 1010, 1011, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 100001 etc. It is easy to see that up to $2^n$, $L$ contains $2^{n-1}-n-1$ numbers. So somewhere around $2^n+n$ the shift happens from NoMaj to Maj, and around $2^n-n$ from Maj to NoMaj. Anyhow, as $n$ can look anything in binary, it is easy to show that the pumping lemma does not hold for $L'$.

$\endgroup$
4

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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