Regularity of “middles” of words from regular language

Question

I need some help with the following problem. Let $L \subseteq \Sigma^*$ be a regular language. I have to prove that the language $P = \{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^*\}$ is regular, where $\Sigma$ is the alphabet. In other words $P$ is the language of all substrings of words from $L$. How do I prove that $P$ is regular?

Answer 1

$L$ is a regular language, so you have a DFA $M$ for it. First remove every “dead” state in $M$, i.e. every state that cannot lead to an accepting state. Make every state in $M$ an accepting state, and make a new start state that $\epsilon$-branches to every state in $M$. The resulting NFA $M'$ recognizes $P$, because:

a) If the string $bac$ was accepted by $M$, then there was a sequence from $Start$ through $S1$ that recognizes $b$, a sequence from $S1$ to $S2$ that recognizes $a$, and a sequence from $S2$ to an accepting state $S3$ that recognizes $c$. But $S1$ is now connected to $Start'$ through $\epsilon$-transitions and $S2$ is an accepting state, hence $M'$ accepts $a$.

b) Conversely, because we have removed transitions that cannot lead to an accepting state, every sequence recognized by $M'$ was part of an accepting sequence for $M$. Because we have not added any edges except those that can be used only to skip $b$, this sequence was consecutive in $M$.

Answer 2

Let $R$ be a regular language. Then there is a finite automaton $M$ for which the language, $L(M)$, of $M$ is $R$. Without loss of generality, we may assume that $M$ has no unreachable states. Construct a new FA, $M'$, as follows:

• For each state $q$ of $M$ which has a sequence of transitions to a final state of $M$, make $q$ a final state. Call the set of such states $S$.
• Add a new start state $q_0$ having $\epsilon$-transitions to each element of $S$.

It's not hard to see that $M'$ will accept any string which is a substring of some string in $R$.

Answer 3

Proving the language is regular

We can prove the language $P$ is regular by using other closure properties. Middles are actually substrings. They are obtained by taking suffixes of prefixes of the original language. Both operations of taking prefixes and taking suffixes applied to regular languages will result in regular languages.

Finding an explicit regular expression for it

In one of the comments the question was narrowed down to: Given a regular expression, can we find a regular expression for the substrings of a language directly, i.e., without intermediate finite state automata?

Interesting. Yes, it can be done. First observe that substrings are suffixes of prefixes. I will explain how to find an expression for prefixes. Then a similar solution works for suffixes, and we can apply both operations in turn.

The solution works recursively, as regular expressions are defined that way. Let $\alpha, \beta$ be regex's. Your own notation may vary.

$\operatorname{pref}(\alpha + \beta ) = \operatorname{pref}(\alpha)+\operatorname{pref}(\beta )$

$\operatorname{pref}(\alpha \cdot \beta ) = \operatorname{pref}(\alpha)+\alpha\cdot\operatorname{pref}(\beta )$

$\operatorname{pref}(\alpha^* ) = \alpha^*\cdot\operatorname{pref}(\alpha )$

Then we should add a base-case.

$\operatorname{pref}(a) = \varepsilon+a$

Answer 4

Given a finite alphabet $\Sigma := \{a, b, \dots\}$, consider the so-called "tagged" alphabet $\Sigma' := \{a', b', \dots\}$. Consider the monoid morphisms $untag, killTag : \Sigma \cup \Sigma' \to \Sigma$ given by

• $untag(a) := a$ for $a \in \Sigma$, $untag(a') := a$ for $a' \in \Sigma'$.
• $killTag(a) := a$ for $a \in \Sigma$, $killTag(a') := \varepsilon$ for $a' \in \Sigma'$.

We can verify that these are indeed monoid morphisms. We know that the class of regular languages is closed under homomorphisms, inverse homomorphisms, and intersection with regular languages. With this in mind we see that

$P = killTag[untag^{-1}[L] \cap \Sigma'^*\Sigma^*\Sigma'^*]$

which is also regular due to the closure properties of regular languages mentioned above.