Prove that REG is closed against removing all but lexicographicaly largest words (per length)

Question

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let

$\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$,

where $L_m = L \cap \Sigma_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.

For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

Answer 1

Here is the basic idea. Suppose that $x0y \in L$. When would $x0y \notin \mathcal{B}(L)$? Exactly when $x1z \in L$ for some $|z| = |y|$. When does that happen? Fix some DFA for $L$, and suppose that after reading $x1$, it is at state $q$. Parikh's theorem shows that the set of lengths $\ell$ such that $x1z \in L$ for some $|z| = \ell$ is eventually periodic, that is, it is of the form $L_0(q) \cup \{k m(q) + a : a \in L_1(q) \text{ and } k \geq 0\}$ for some finite $L_0(q),L_1(q)$. We can further assume that $m(q) = m$ is the same for all states $q$, since there are only finitely many of them and we can take the LCM of the minimal periods.

As we read more and more zeroes, we obtain more and more constraints, which can be summarized in the form: the word cannot end in $\ell$ characters for $\ell \in L_0 + \{ km + a : a \in L_1 \}$. Note that there are only finitely many possibilities for $L_0$ and $L_1$, since $\max L_0 \leq \max_q \max L_0(q)$, and similarly for $L_1$. This means that we can store and maintain this information in a finite state automaton, and use it to decide $\mathcal{B}(L)$.

Answer 2

Consider the language $\mathrm{less}(L)$ of all strings that are of the same length as one in $L$ but lexicographically less. For a two letter alphabet these are strings of the form $x0z$ with $x1y\in L$ and $|y|=|z|$.

Now $\mathrm{less}(L)$ is regular, and can be accepted by a nondeterministic automaton. It runs as the original automaton $\mathcal A$ for $L$, but at some nondeterministic point, when $\mathcal A$ reads a $1$, then the new automaton reads a $0$. Now the new automaton reads any letter (from $z$), and takes a step on whatever letter in $\mathcal A$ (the corresponding $y$). It accepts when this simulation accepts.

If everything goes well, then $\mathcal B(L) = L - \mathrm{less}(L)$ is regular.