4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ You may benefit from reading this answer by Yuval to a similar question. $\endgroup$
    – John L.
    Sep 27, 2021 at 7:53
  • $\begingroup$ Indeed. It is a very good advice to read that answer by Yuval, as suggested by JohnL. The solution to both problems uses two automata-tricks. (1) nondeterminism, the NFA guesses one or more intermediate states in advance. (2) parallelism, the NFA simulates two copies of the original automaton in parallel. In the earlier answer the original computation is split into the first and second half, in the current problem that split is more complicated. $\endgroup$ Sep 27, 2021 at 9:36

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Nice answer. The theory of monoids is cool. $\endgroup$
    – John L.
    Oct 27, 2021 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.