Is the language "substrings of a regular language that are over half the length of the superstring" regular?

Question

We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular?

I was provided the following solution, but I don't understand it:

Let M be a DFA that recognizes B. Construct an NFA $N$ that accepts its input $x$ if $x$ is a major substring of some string $y ∈ B$, that is, if $y = uxv ∈ L(M)$ for some string $u$ and $v$ where $|x| ≥ |u| + |v|$. Informally, $N$ uses its nondeterminism to guess the appropriate $y$ as follows. First, $N$ guesses the state $q_1$ that it is in just before it reads the first symbol of $x$ and the state $q_2$ that it is in just after it reads the last symbol of $x$. Then it reads $x$ and checks that $x$ takes $M$ from $q_1$ to $q_2$. In parallel with reading the symbols of $x$ and performing that check, $N$ guesses the symbols of $u$ followed by the symbols of $v$, and checks that $u$ takes M from its start state to $q_1$ and that $v$ takes $M$ from $q_2$ to an accept state. Because $|x| ≥ |u| + |v|$, the machine $N$ has enough time to guess both $u$ and $v$, while it is reading $x$.

What exactly is meant by "$N$ guessing the state that it's in"? Does it iterate over $Q \times Q$ and check if $x$ takes $M$ from $q_1$ to $q_2$? If so, is it done by parallelizing these $|Q|^2$ "lines of thought"?

How is it that $N$ can guess the symbols of $u$ and $v$? It seems to me that there are infinite possibilities for $u$ and $v$, and so iterating over these is beyond the capabilities of an $NFA$.

Lastly, how do we guarantee that the guessed $u$ and $v$ have a combined length no more than that of $x$? Counting is outside of the capabilities of an NFA, so I don't think it should be able to count $x$'s length (call it $k$) and try every $s \in \Sigma^k$.

Answer 1

The solution provided is pretty concise.

"First, $N$ guesses the state $q_1$ that it is in just before it reads the first symbol of $x$ and the state $q_2$ that it is in just after it reads the last symbol of $x$." That means $N$ is the union of $|Q|^2$ $\text{NFA}$. (That means, running $N$ will be the same as running all those $\text{NFA}$s. $N$ accepts a word iff at least one of those $\text{NFA}$ accepts the word). We can label them $N_{q_1, q_2}$ where both $q_1$ and $q_2$ range over all states of $M$ independently. $N_{q_1, q_2}$ will be constructed to accept the words $$\{x\in \Sigma^* \mid\text{there exist } u, v\in \Sigma^* \text{ such that } uxv\in L(M)\\ \text{ and } |x| ≥ |u| + |v|\\ \text{ and, if starting at state }q_1 \text{ and given input }x, \ M \text{ will go to }q_2 \}.$$

Here is a description of $N_{q_1, q_2}$. Running $N_{q_1, q_2}$ will be the same as running one DFA and one NFA in parallel. $N_{q_1,q_2}$ accepts a word if and only if that DFA and that NFA both accept.

The $\text{DFA}$ for $N_{q_1, q_2}$ is the same $M$ except that its start state is $q_1$ and its only accept state is $q_2$.

The $\text{NFA}$ for $N_{q_1, q_2}$ has states $(r, t)$, where $s$ and $t$ range over all states of $M$ independently. (So, there are $|Q|^2$ states). $(S, q_2)$ is the start state of this $\text{NFA}$, where $S$ is the start state of $M$. For each accept state of $M$, $(q_1, M)$ is an accept state of this NFA. In each step, regardless of what is the current input symbol, this $\text{NFA}$ will go from its current state $(r, t)$ to either $(r', t)$ where $r'$ is some state of $M$ that is immediately reachable from $r$ or $(r, t')$ where $t'$ is some state of $M$ that is immediately reachable from $t$. However, if the current state is an accept state, this $\text{NFA}$ will remain in that accept state forever.

You can view this $\text{NFA}$ for $N_{q_1, q_2}$ as running two copies of $M$, one from the start state of $M$ and one from the state $q_2$. In each step, it will either run the first copy or the second copy, indeterministically. This $\text{NFA}$ accepts once the first copy reaches $q_1$ and the second copy reaches an accept state of $M$, and it will not change state thereafter. So, when given input $x$ and running in parallel with the $\text{DFA}$ for $N_{q_1, q_2}$, this $\text{NFA}$ for $N_{q_1, q_2}$ is just checking whether within $|x|$ steps it will reach one of its accept states. That is how "$N$ can guess the symbols of $u$ and $v$" even if there might be "infinite possibilities for $u$ and $v$", as well as "guarantee that the guessed $u$ and $v$ have a combined length no more than that of $x$".

---

Exercise. Fix a positive integer $k$. We say $x$ is a $\frac 1k$-significant substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq\frac1k |y|$. Show that if $B$ is a regular language, the set of $\frac 1k$-significant substrings of strings in $B$ is a regular language.

Answer 2

The given solution is a kind of hand-waving proof, so the proof by John L. is highly preferable. Here is a different proof, which relies on the notions of recognisable and rational subsets of a monoid. See the definitions below and [1, Chapter 3] for more details. The proof relies on the following known facts:

1. In a finitely generated free monoid, recognisable and rational subsets coincide (and are usually called regular). These two notions usually do not coincide in arbitrary monoids.
2. Let $L$ be a regular language of $A^*$. Then the set $$ T = \{ (u_1, u_2, u_3) \in A^* \times A^* \times A^* \mid u_1u_2u_3 \in L \} $$ is a recognisable subset of $A^* \times A^* \times A^*$. This result is originally due to Conway [2], a short proof can be found in [3, Theorem 5.7].
3. The set $$ S = \{ (u_1, u_2, u_3) \in A^* \times A^* \times A^* \mid |u_1| + |u_3| \leqslant |u_2 \}| $$ is a rational subset of $A^* \times A^* \times A^*$. Indeed $S = R^*$, with $$ R = \{(1, a, b), (b, a, 1), (1, a, 1) \mid a, b \in A\} $$
4. The intersection of a rational subset and a recognisable subset of a monoid is rational. See [1, Chapter 3, Proposition 2.6] for a proof. Thus $T \cap S$ is a rational subset of $A^* \times A^* \times A^*$.
5. Rational sets are preserved under monoid morphisms. In particular, since the projection $p_2: A^* \times A^* \times A^* \to A^*$ defined by $p_2(u_1, u_2, u_3) = u_2$ is a morphism, it preserves rational subsets. Thus the language $M = p_2(T \cap S)$ is rational.
6. The language $M$ is nothing else than the set of "majority factors" of $L$ and thus it is regular.

The proof is sufficiently flexible to be adapted to solve similar questions.

Reminder of definitions. Let $M$ be a monoid. A subset $L$ of a $M$ is recognisable if there exists a finite monoid $F$, a monoid morphism $f: M \rightarrow F$ and a subset $P$ of $F$ such that $L = f^{-1}(P)$.

The set of rational subsets of $M$ is the smallest set of subsets of $M$ containnig the empty set and the singletons and closed under finite union, product and star (here $X^*$ is the submonoid generated by $X$).

References

[1] J. Berstel, Transductions and context-free languages, Teubner, 1979.

[2] J.H. Conway, Regular Algebra and Finite Machines, Chapman and Hall, London, 1971.

[3] J.-É. Pin, How to prove that a language is regular or star-free?, LATA 2020, LNCS 12038 (2020) 68-88.