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

CC BY-SA 4.0
2022-10-08T21:12:28.727Z
Do you mean $L=10\{0,1\}^*1\{0,1\}^*$?
Neal Young
CC BY-SA 4.0
2022-10-08T21:41:59.867Z
Yes. $~$ $~$ $ $
domotorp
CC BY-SA 4.0
2022-10-08T22:38:08.280Z
Thanks so much! Is there a reference for this, or did you come up with this yourself?
Jake
CC BY-SA 4.0
2022-10-09T04:51:32.763Z
Here is the reference: 
@MISC {51984,
    TITLE = {Check whether DFA accepts majority of words less than a cutoff with another DFA},
    AUTHOR = {domotorp (https://cstheory.stackexchange.com/users/419/domotorp)},
    HOWPUBLISHED = {Theoretical Computer Science Stack Exchange},
    NOTE = {URL:https://cstheory.stackexchange.com/q/51984 (version: 2022-10-08)},
    EPRINT = {https://cstheory.stackexchange.com/q/51984},
    URL = {https://cstheory.stackexchange.com/q/51984}
}
domotorp
CC BY-SA 4.0
2022-10-08T20:51:08.940Z
2022-10-08T20:51:08.940Z
domotorp
<h3>Question</h3>
<p>Let <span class="math-container">$M$</span> be some DFA that reads integers in base <span class="math-container">$k$</span>. Does there always exist some other DFA <span class="math-container">$M'$</span> that also reads integers in base <span class="math-container">$k$</span>, where <span class="math-container">$M'(x)$</span> accepts if and only if <span class="math-container">$M$</span> accepts the majority of words less than <span class="math-container">$x$</span>?</p>
<h3>Background and motivation</h3>
<p>According to the cited paper, the above process works if we replace &quot;majority&quot; with &quot;modulo <span class="math-container">$p$</span>&quot; for some constant <span class="math-container">$p$</span>; that is, we can build a second DFA <span class="math-container">$M'$</span> where <span class="math-container">$M'(x)$</span> accepts if and only if <span class="math-container">$M$</span> accepts 0 mod <span class="math-container">$p$</span> words less than <span class="math-container">$x$</span>. However, this is still in some sense a very &quot;regular&quot; task, in the sense that DFAs can calculate the number of 1s in a string mod <span class="math-container">$p$</span>, so I am curious to see whether it extends to a simple problem that is not &quot;regular&quot; in the same way.</p>
<p><em>Lecomte, P. B. A.; Rigo, M.</em>, <a href="http://dx.doi.org/10.1007/s002240010014" rel="noreferrer"><strong>Numeration systems on a regular language</strong></a>, Theory Comput. Syst. 34, No. 1, 27-44 (2001). <a href="https://zbmath.org/?q=an:0969.68095" rel="noreferrer">ZBL0969.68095</a>.</p>

CC BY-SA 4.0
2022-10-09T16:22:15.017Z
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?
Neal Young
CC BY-SA 4.0
2022-10-09T19:59:57.073Z
@NealYoung I'm assuming that $M$ is insensitive to leading 0s.
Jake
<automata-theory><regular-language>
Check whether DFA accepts majority of words less than a cutoff with another DFA
Jake
# Check whether DFA accepts majority of words less than a cutoff with another DFA

(Asked by: username_0 on 2022-10-02)

### 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**](http://dx.doi.org/10.1007/s002240010014), Theory Comput. Syst. 34, No. 1, 27-44 (2001). [ZBL0969.68095](https://zbmath.org/?q=an:0969.68095).

**Tags:** automata-theory, regular-language
> **Comments:**
> **username_1**: 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?  
> **username_0**: @NealYoung I'm assuming that $M$ is insensitive to leading 0s.  

---

## 1 answers

### Answer by username_2 on 2022-10-08. Score: 2 | Accepted answer

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

> **Comments:**
> **username_1**: Do you mean $L=10\{0,1\}^*1\{0,1\}^*$?  
> **username_2**: Yes. $~$ $~$ $ $  
> **username_0**: Thanks so much! Is there a reference for this, or did you come up with this yourself?  
> **username_2**: Here is the reference:  @MISC {51984,     TITLE = {Check whether DFA accepts majority of words less than a cutoff with another DFA},     AUTHOR = {domotorp (https://cstheory.stackexchange.com/users/419/domotorp)},     HOWPUBLISHED = {Theoretical Computer Science Stack Exchange},     NOTE = {URL:https://cstheory.stackexchange.com/q/51984 (version: 2022-10-08)},     EPRINT = {https://cstheory.stackexchange.com/q/51984},     URL = {https://cstheory.stackexchange.com/q/51984} }  

---

