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