<p>There exists a context-free language <span class="math-container">$M$</span>, such that <span class="math-container">$N(M)$</span> is not semilinear.
The construction is a modification of the construction I shared in the comments.</p>
<p>Indeed, consider the language <span class="math-container">$K := \{ a^{2i} ba^i \mid i \geqslant 1\}$</span>.
Obviously, <span class="math-container">$K$</span> is context-free. Therefore, <span class="math-container">$L := K^{+} (aa)^{*} ab$</span> also is. Finally, <span class="math-container">$M := L^{+}$</span> is also a context-free language. I claim that <span class="math-container">$N(M)$</span> is not semilinear.</p>
<p>Indeed, let's consider an arbitrary word of the type <span class="math-container">$(a^m b)^n$</span> from the language <span class="math-container">$L$</span> (here, <span class="math-container">$m$</span> and <span class="math-container">$n$</span> don't have to be equal). It necessarily has <span class="math-container">$m \geqslant 1$</span> and <span class="math-container">$n \geqslant 2$</span>.</p>
<p>An arbitrary word from <span class="math-container">$L$</span> looks like <span class="math-container">$w_1 w_2 \ldots w_d a^{2t + 1} b$</span>, where <span class="math-container">$d \geqslant 1$</span>, <span class="math-container">$t \geqslant 0$</span> and all the words <span class="math-container">$w_i$</span> are in the language <span class="math-container">$K$</span>. Hence, if the word <span class="math-container">$(a^m b)^n$</span> is in <span class="math-container">$L$</span>, then <span class="math-container">$w_1 = a^m b a^{m/2}$</span> (and <span class="math-container">$m$</span> has to be even), <span class="math-container">$w_2 = a^{m/2} ba^{m/4}$</span>, <span class="math-container">$w_3 = a^{3m/4} ba^{3m/8}$</span>, <span class="math-container">$\ldots$</span>, <span class="math-container">$w_d = a^{m \cdot p_d / 2^{d-1}} b a^{m \cdot p_d / 2^d}$</span>. Here, <span class="math-container">$p_1$</span>, <span class="math-container">$p_2$</span>, <span class="math-container">$\ldots$</span>, <span class="math-container">$p_d$</span> are the numerators of the fractions that appear in the definitions of <span class="math-container">$w_i$</span>. For example, <span class="math-container">$p_1 = 1, p_2 = 1, p_3 = 3, p_4 = 5, p_5 = 11$</span>, et cetera. It can be proven via induction that all <span class="math-container">$p_i$</span>'s are odd. Moreover, <span class="math-container">$p_i / 2^{i-1}$</span> and <span class="math-container">$p_i / 2^i$</span> are successive binary approximations of <span class="math-container">$2/3$</span> and <span class="math-container">$1/3$</span> respectively (but this is not important here).</p>
<p>It is not hard to see that <span class="math-container">$n = d + 1$</span>. Indeed, each <span class="math-container">$w_i$</span> contains exactly one letter <span class="math-container">$b$</span> and so does the word <span class="math-container">$a^{2t+1}b$</span>. Moreover, <span class="math-container">$m$</span> is divisible by <span class="math-container">$2^d$</span> (because <span class="math-container">$p_d$</span> is odd). Finally, the last block of <span class="math-container">$a$</span>-s contains exactly <span class="math-container">$(2t + 1) + (m \cdot p_d / 2^d)$</span> letters. On the other hand, it should contain <span class="math-container">$m$</span> letters. Therefore, <span class="math-container">$m$</span> can't be divisible by <span class="math-container">$2^{d+1}$</span>: otherwise, the sum of an odd number <span class="math-container">$2t+1$</span> and an even number <span class="math-container">$m \cdot p_d / 2^d$</span> would be an even number <span class="math-container">$m$</span>.</p>
<p>Hence, if a word <span class="math-container">$(a^m b)^n$</span> is in <span class="math-container">$L$</span>, then <span class="math-container">$m \geqslant 1$</span>, <span class="math-container">$n \geqslant 2$</span> and <span class="math-container">$m$</span> is exactly divisible by <span class="math-container">$2^{n-1}$</span> (in the sense that <span class="math-container">$m$</span> is divisible by <span class="math-container">$2^{n-1}$</span>, but not by <span class="math-container">$2^n$</span>). Moreover, the converse statement is true as well: if <span class="math-container">$m \geqslant 1$</span>, <span class="math-container">$n \geqslant 2$</span> and <span class="math-container">$m$</span> is exactly divisible by <span class="math-container">$2^{n-1}$</span>, then <span class="math-container">$(a^m b)^n \in L$</span>.</p>
<p>Finally, consider a word of the type <span class="math-container">$(a^m b)^m \in M$</span>. Suppose that <span class="math-container">$m$</span> is exactly divisible by <span class="math-container">$2^{n-1}$</span> for some <span class="math-container">$n \geqslant 2$</span>. Recall that <span class="math-container">$M$</span> is a concatenation of several words from <span class="math-container">$L$</span>. All these words should be of form <span class="math-container">$(a^m b)^{*}$</span> (and <span class="math-container">$(a^m b)^n$</span> is the only word of this form  in the language <span class="math-container">$L$</span>). Therefore, if <span class="math-container">$(a^m b)^m \in M$</span>, then <span class="math-container">$m$</span> is divisible by <span class="math-container">$n$</span>. Similarly to the above paragraph, the converse implication is also true.</p>
<p>All in all, <span class="math-container">$m \in N(M)$</span> if and only if one of the following conditions is true:</p>
<ol>
<li><span class="math-container">$m \equiv 2 \pmod 4$</span> and <span class="math-container">$m$</span> is divisible by <span class="math-container">$1 + 1 = 2$</span> (the second condition is redundant).</li>
<li><span class="math-container">$m \equiv 4 \pmod 8$</span> and <span class="math-container">$m$</span> is divisible by <span class="math-container">$2 + 1 = 3$</span>.</li>
<li><span class="math-container">$m \equiv 8 \pmod {16}$</span> and <span class="math-container">$m$</span> is divisble by <span class="math-container">$3 + 1 = 4$</span> (the second condition is redundant).</li>
<li><span class="math-container">$m \equiv 16 \pmod {32}$</span> and <span class="math-container">$m$</span> is divisible by <span class="math-container">$4 + 1 = 5$</span>.</li>
<li><span class="math-container">$m \equiv 32 \pmod {64}$</span> and <span class="math-container">$m$</span> is divisible by <span class="math-container">$5 + 1 = 6$</span> (the second condition is not completely redundant, but <span class="math-container">$6$</span> can be replaced with <span class="math-container">$3$</span>).</li>
<li>Et cetera.</li>
</ol>
<p>Intuitively, <span class="math-container">$N(M)$</span> doesn't look like a semilinear set at all.</p>
<p>Formally speaking, suppose that <span class="math-container">$N(M)$</span> is periodic with a period <span class="math-container">$\ell$</span>. Then, <span class="math-container">$\ell$</span> can't be odd, as all numbers in <span class="math-container">$N(M)$</span> are even.
Moreover, the case when <span class="math-container">$\ell \equiv 2 \pmod 4$</span> is also impossible. Indeed, we can pick a large enough number <span class="math-container">$q$</span> that is exactly divisible by <span class="math-container">$4$</span>, but <em>is not</em> divisible by <span class="math-container">$3$</span>. Then, <span class="math-container">$q \notin N(M)$</span>, but <span class="math-container">$q - \ell \equiv 2 \pmod 4$</span>, implying  <span class="math-container">$q - \ell \in N(M)$</span>.</p>
<p>Similarly, the case <span class="math-container">$\ell \equiv 4 \pmod 8$</span> is also impossible. Indeed, pick a large enough number <span class="math-container">$q$</span>, such that <span class="math-container">$q \equiv 16 \pmod {32}$</span>, <span class="math-container">$q \not\equiv 0 \pmod 5$</span> and <span class="math-container">$q \equiv \ell \pmod 3$</span> (this is possible by the Chinese remainder theorem). Then, <span class="math-container">$q \notin N(M)$</span>. But, on the other hand, <span class="math-container">$q - \ell \equiv 4 \pmod 8$</span> and <span class="math-container">$q - \ell$</span> is divisible by <span class="math-container">$3$</span>, implying <span class="math-container">$q - \ell \in N(M)$</span>.</p>
<p>We can proceed in the same fashion: if <span class="math-container">$\ell \equiv 2^u \pmod {2^{u+1}}$</span>, then we need to consider some large enough <span class="math-container">$q$</span>, such that <span class="math-container">$q \notin N(M)$</span>, but <span class="math-container">$q - \ell \in N(M)$</span>. If <span class="math-container">$u$</span> is odd, then some <span class="math-container">$q$</span> satisfying <span class="math-container">$q \equiv 2^{u+1} \pmod {2^{u+2}}$</span> will do. If <span class="math-container">$u$</span> is even, then we can pick a <span class="math-container">$q$</span> with <span class="math-container">$q \equiv 2^{u+2} \pmod {2^{u+3}}$</span>.</p>
<p>We can make the argument above slightly simpler by replacing <span class="math-container">$K^{+}$</span> in the definition of <span class="math-container">$L$</span> with <span class="math-container">$(KK)^+$</span>, forcing <span class="math-container">$d$</span> to be even and <span class="math-container">$n = d + 1$</span> to be odd.</p>

CC BY-SA 4.0
2022-04-27T11:58:22.933Z
That's a nice proof! I think we can further simplify it by choosing $K = \{ a^{2m} b a^{m+n} b a^n : m, n \geq 0 \}$ and $L = (K^+ \cap (a+b)^* b a) (a+b)^*$. Then $N(L) = \{ 2^n : n \geq 3 \}$.
Ilkka Törmä
CC BY-SA 4.0
2022-04-25T03:49:07.963Z
2022-04-25T04:24:53.377Z
2022-04-25T04:24:53.377Z
Kaban-5
<h2>Question</h2>
<p>For a language <span class="math-container">$L \subset \{a,b\}^*$</span>, denote <span class="math-container">$N(L) = \{ n \geq 0 \mid (a^n b)^n \in L \}$</span>.
If <span class="math-container">$L$</span> is context-free, is <span class="math-container">$N(L)$</span> necessarily semilinear, meaning that <span class="math-container">$n \in N(L) \iff n+p \in N(L)$</span> for some constant <span class="math-container">$p \geq 1$</span> and large enough <span class="math-container">$n$</span>?</p>
<h2>Thoughts</h2>
<p>If <span class="math-container">$L$</span> is regular, then <span class="math-container">$N(L)$</span> is semilinear.
This can be shown e.g. by noticing that the syntactic congruence class of <span class="math-container">$a^n$</span> depends only on <span class="math-container">$n$</span> modulo some constant, and within each of these finitely many congruence classes, the class of <span class="math-container">$(a^n b)^k$</span> depends only on <span class="math-container">$k$</span> modulo another constant.</p>
<p>If <span class="math-container">$L$</span> is context-free, my first instinct was to repeatedly use Ogden's lemma or its generalizations to pump <span class="math-container">$(a^n b)^n$</span> into <span class="math-container">$(a^{n+k} b)^n$</span> for some fixed <span class="math-container">$k \geq 1$</span>, and then try to pump the outer <span class="math-container">$n$</span>.
But we can't always pump only the <span class="math-container">$a$</span>-parts: the grammar
<span class="math-container">$$
S \to ab \mid aSa^+b
$$</span>
produces the language <span class="math-container">$L \subset (a^+b)^+$</span> where the <span class="math-container">$b$</span>-symbols match the <span class="math-container">$a$</span>-symbols of the first <span class="math-container">$a$</span>-part, so if you pump away some of those <span class="math-container">$a$</span>s, you have to remove some <span class="math-container">$b$</span>s as well.
Even if you manage to pump only <span class="math-container">$a$</span>-runs, you may have to pump them by different amounts: the grammar
<span class="math-container">$$
S \to a^*b S \mid S a^*b \mid MNb \\
M \to aaMa \mid b \\
N \to aNaa \mid b
$$</span>
produces <span class="math-container">$L \subset (a^* b)^+$</span> where some three consecutive <span class="math-container">$a$</span>-runs <span class="math-container">$a^i$</span>, <span class="math-container">$a^j$</span>, <span class="math-container">$a^k$</span> satisfy <span class="math-container">$2j = i+k$</span>.
Pumping the middle run requires us to pump one of the others by twice that amount, or all three at the same time.
Of course, all sorts of mixes of these examples are possible.</p>
<p>Parikh's theorem seems useless, since <span class="math-container">$N(L)$</span> doesn't tell us much about the Parikh vectors of <span class="math-container">$L$</span>.</p>

CC BY-SA 4.0
2022-04-23T08:00:29.647Z
I think that it is easiest to show that $N_2(L) = \{ m,n \geq 0 \mid (a^m b)^n \in L \}$ is semilinear, and that would also imply that $N(L)$ is semilinear.
domotorp
CC BY-SA 4.0
2022-04-24T15:50:12.510Z
@domotorp: $N_2(L)$ doesn't have to be semilinear (in fact, I don't believe that $N(L)$ has to be semilinear either; but I can't prove that it doesn't have to be). Indeed, consider the language $K = \{ a^{2i} ba^i \mid i \geqslant 1\}$. Obviously, $K$ is context-free. Therefore, $L := K^{+} a^{*} b$ also is. Consider a word $(a^m b)^n \in L$. Then, the first "block" from $K$ is $a^m b a^{m/2}$, the second is $a^{m/2} b a^{m/4}$, the third is $a^{3m/4} b a^{3m/8}$, e t. c. ($a^* b$ in the definition of $L$ is necessary to ensure that the last block of $a$-s is also of size $m$).
Kaban-5
CC BY-SA 4.0
2022-04-24T15:51:22.407Z
@domotorp: all in all, it is easy to see that we can have $n$ blocks of $a$-s if and only if $m$ is divisible by $2^n$. Hence, $N_2(L)$ is the set $\{(m, n) \mid m \geqslant 1, n \geqslant 1 \text{ and } m \text{ is divisible by }  2^n\}$. In this set, the second coordinate grows logarithmically with $m$. Therefore, it can't be semilinear.
Kaban-5
CC BY-SA 4.0
2022-04-24T17:01:35.670Z
@Kaban-5 Brilliant construction!
domotorp
<fl.formal-languages><context-free>
Words of the form $(a^n b)^n$ in a context-free language
Ilkka Törmä
# Words of the form $(a^n b)^n$ in a context-free language

(Asked by: username_0 on 2022-04-21)

## Question

For a language $L \subset \{a,b\}^\*$, denote $N(L) = \{ n \geq 0 \mid (a^n b)^n \in L \}$.
If $L$ is context-free, is $N(L)$ necessarily semilinear, meaning that $n \in N(L) \iff n+p \in N(L)$ for some constant $p \geq 1$ and large enough $n$?

## Thoughts

If $L$ is regular, then $N(L)$ is semilinear.
This can be shown e.g. by noticing that the syntactic congruence class of $a^n$ depends only on $n$ modulo some constant, and within each of these finitely many congruence classes, the class of $(a^n b)^k$ depends only on $k$ modulo another constant.

If $L$ is context-free, my first instinct was to repeatedly use Ogden's lemma or its generalizations to pump $(a^n b)^n$ into $(a^{n+k} b)^n$ for some fixed $k \geq 1$, and then try to pump the outer $n$.
But we can't always pump only the $a$-parts: the grammar
$$
S \to ab \mid aSa^+b
$$
produces the language $L \subset (a^+b)^+$ where the $b$-symbols match the $a$-symbols of the first $a$-part, so if you pump away some of those $a$s, you have to remove some $b$s as well.
Even if you manage to pump only $a$-runs, you may have to pump them by different amounts: the grammar
$$
S \to a^\*b S \mid S a^\*b \mid MNb \\
M \to aaMa \mid b \\
N \to aNaa \mid b
$$
produces $L \subset (a^\* b)^+$ where some three consecutive $a$-runs $a^i$, $a^j$, $a^k$ satisfy $2j = i+k$.
Pumping the middle run requires us to pump one of the others by twice that amount, or all three at the same time.
Of course, all sorts of mixes of these examples are possible.

Parikh's theorem seems useless, since $N(L)$ doesn't tell us much about the Parikh vectors of $L$.

**Tags:** fl.formal-languages, context-free

> **Comments:**
> **username_1**: I think that it is easiest to show that $N_2(L) = \{ m,n \geq 0 \mid (a^m b)^n \in L \}$ is semilinear, and that would also imply that $N(L)$ is semilinear.  
> **username_2**: @username_1: $N_2(L)$ doesn't have to be semilinear (in fact, I don't believe that $N(L)$ has to be semilinear either; but I can't prove that it doesn't have to be). Indeed, consider the language $K = \{ a^{2i} ba^i \mid i \geqslant 1\}$. Obviously, $K$ is context-free. Therefore, $L := K^{+} a^{*} b$ also is. Consider a word $(a^m b)^n \in L$. Then, the first "block" from $K$ is $a^m b a^{m/2}$, the second is $a^{m/2} b a^{m/4}$, the third is $a^{3m/4} b a^{3m/8}$, e t. c. ($a^* b$ in the definition of $L$ is necessary to ensure that the last block of $a$-s is also of size $m$).  
> **username_2**: @username_1: all in all, it is easy to see that we can have $n$ blocks of $a$-s if and only if $m$ is divisible by $2^n$. Hence, $N_2(L)$ is the set $\{(m, n) \mid m \geqslant 1, n \geqslant 1 \text{ and } m \text{ is divisible by }  2^n\}$. In this set, the second coordinate grows logarithmically with $m$. Therefore, it can't be semilinear.  
> **username_1**: @username_2 Brilliant construction!  

---

## 1 answers

### Answer by username_2 on 2022-04-25. Score: 5 | Accepted answer

There exists a context-free language $M$, such that $N(M)$ is not semilinear.
The construction is a modification of the construction I shared in the comments.

Indeed, consider the language $K := \{ a^{2i} ba^i \mid i \geqslant 1\}$.
Obviously, $K$ is context-free. Therefore, $L := K^{+} (aa)^{\*} ab$ also is. Finally, $M := L^{+}$ is also a context-free language. I claim that $N(M)$ is not semilinear.

Indeed, let's consider an arbitrary word of the type $(a^m b)^n$ from the language $L$ (here, $m$ and $n$ don't have to be equal). It necessarily has $m \geqslant 1$ and $n \geqslant 2$.

An arbitrary word from $L$ looks like $w\_1 w\_2 \ldots w\_d a^{2t + 1} b$, where $d \geqslant 1$, $t \geqslant 0$ and all the words $w\_i$ are in the language $K$. Hence, if the word $(a^m b)^n$ is in $L$, then $w\_1 = a^m b a^{m/2}$ (and $m$ has to be even), $w\_2 = a^{m/2} ba^{m/4}$, $w\_3 = a^{3m/4} ba^{3m/8}$, $\ldots$, $w\_d = a^{m \cdot p\_d / 2^{d-1}} b a^{m \cdot p\_d / 2^d}$. Here, $p\_1$, $p\_2$, $\ldots$, $p\_d$ are the numerators of the fractions that appear in the definitions of $w\_i$. For example, $p\_1 = 1, p\_2 = 1, p\_3 = 3, p\_4 = 5, p\_5 = 11$, et cetera. It can be proven via induction that all $p\_i$'s are odd. Moreover, $p\_i / 2^{i-1}$ and $p\_i / 2^i$ are successive binary approximations of $2/3$ and $1/3$ respectively (but this is not important here).

It is not hard to see that $n = d + 1$. Indeed, each $w\_i$ contains exactly one letter $b$ and so does the word $a^{2t+1}b$. Moreover, $m$ is divisible by $2^d$ (because $p\_d$ is odd). Finally, the last block of $a$-s contains exactly $(2t + 1) + (m \cdot p\_d / 2^d)$ letters. On the other hand, it should contain $m$ letters. Therefore, $m$ can't be divisible by $2^{d+1}$: otherwise, the sum of an odd number $2t+1$ and an even number $m \cdot p\_d / 2^d$ would be an even number $m$.

Hence, if a word $(a^m b)^n$ is in $L$, then $m \geqslant 1$, $n \geqslant 2$ and $m$ is exactly divisible by $2^{n-1}$ (in the sense that $m$ is divisible by $2^{n-1}$, but not by $2^n$). Moreover, the converse statement is true as well: if $m \geqslant 1$, $n \geqslant 2$ and $m$ is exactly divisible by $2^{n-1}$, then $(a^m b)^n \in L$.

Finally, consider a word of the type $(a^m b)^m \in M$. Suppose that $m$ is exactly divisible by $2^{n-1}$ for some $n \geqslant 2$. Recall that $M$ is a concatenation of several words from $L$. All these words should be of form $(a^m b)^{\*}$ (and $(a^m b)^n$ is the only word of this form in the language $L$). Therefore, if $(a^m b)^m \in M$, then $m$ is divisible by $n$. Similarly to the above paragraph, the converse implication is also true.

All in all, $m \in N(M)$ if and only if one of the following conditions is true:

1. $m \equiv 2 \pmod 4$ and $m$ is divisible by $1 + 1 = 2$ (the second condition is redundant).
2. $m \equiv 4 \pmod 8$ and $m$ is divisible by $2 + 1 = 3$.
3. $m \equiv 8 \pmod {16}$ and $m$ is divisble by $3 + 1 = 4$ (the second condition is redundant).
4. $m \equiv 16 \pmod {32}$ and $m$ is divisible by $4 + 1 = 5$.
5. $m \equiv 32 \pmod {64}$ and $m$ is divisible by $5 + 1 = 6$ (the second condition is not completely redundant, but $6$ can be replaced with $3$).
6. Et cetera.

Intuitively, $N(M)$ doesn't look like a semilinear set at all.

Formally speaking, suppose that $N(M)$ is periodic with a period $\ell$. Then, $\ell$ can't be odd, as all numbers in $N(M)$ are even.
Moreover, the case when $\ell \equiv 2 \pmod 4$ is also impossible. Indeed, we can pick a large enough number $q$ that is exactly divisible by $4$, but *is not* divisible by $3$. Then, $q \notin N(M)$, but $q - \ell \equiv 2 \pmod 4$, implying $q - \ell \in N(M)$.

Similarly, the case $\ell \equiv 4 \pmod 8$ is also impossible. Indeed, pick a large enough number $q$, such that $q \equiv 16 \pmod {32}$, $q \not\equiv 0 \pmod 5$ and $q \equiv \ell \pmod 3$ (this is possible by the Chinese remainder theorem). Then, $q \notin N(M)$. But, on the other hand, $q - \ell \equiv 4 \pmod 8$ and $q - \ell$ is divisible by $3$, implying $q - \ell \in N(M)$.

We can proceed in the same fashion: if $\ell \equiv 2^u \pmod {2^{u+1}}$, then we need to consider some large enough $q$, such that $q \notin N(M)$, but $q - \ell \in N(M)$. If $u$ is odd, then some $q$ satisfying $q \equiv 2^{u+1} \pmod {2^{u+2}}$ will do. If $u$ is even, then we can pick a $q$ with $q \equiv 2^{u+2} \pmod {2^{u+3}}$.

We can make the argument above slightly simpler by replacing $K^{+}$ in the definition of $L$ with $(KK)^+$, forcing $d$ to be even and $n = d + 1$ to be odd.

> **Comments:**
> **username_0**: That's a nice proof! I think we can further simplify it by choosing $K = \{ a^{2m} b a^{m+n} b a^n : m, n \geq 0 \}$ and $L = (K^+ \cap (a+b)^* b a) (a+b)^*$. Then $N(L) = \{ 2^n : n \geq 3 \}$.  

---

