# Check whether DFA accepts majority of words less than a cutoff with another DFA

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

• 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? Oct 9, 2022 at 16:22
• @NealYoung I'm assuming that $M$ is insensitive to leading 0s.
– Jake
Oct 9, 2022 at 19:59

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'$$.
• Do you mean $L=10\{0,1\}^*1\{0,1\}^*$? Oct 8, 2022 at 21:12
• Yes. $~$ $~$  Oct 8, 2022 at 21:41