Regularity of “middles” of words from regular language

I need some help with the following problem: $L$ - regular language and i have to prove that the language $P$ = {$\alpha$| $\beta\alpha\gamma \in L$, $\beta,\gamma \in (A)^*$} is regular. In other words $P$ is the language of all parts of words from $L$.

Thanks a lot!

-

migrated from cstheory.stackexchange.comDec 24 '12 at 21:58

This question came from our site for theoretical computer scientists and researchers in related fields.

What have you tried? Please detail your attempts. – Shaull Jun 9 '14 at 14:05
This doesn't really warrant a full answer, but as for the name, this is known as the "factor closure" of the given language ("factor" being formal language-ese for substrings). – Klaus Draeger Jun 9 '14 at 16:55
@HendrikJan, Is it possible to write the new language by a regex? stackoverflow.com/questions/24114297/… – Tim Jun 9 '14 at 21:09

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

-
Thanks.Is it possible to write the new language by a regex? stackoverflow.com/questions/24114297/… – Tim Jun 9 '14 at 21:09
@Tim Of course it is possible. Any language that can be recognized by a FSM has a regex. Albeit, not a "nice" regex, necessarily. – Kaz Jun 9 '14 at 22:29
@Tim: See our reference question on how to transform FAs into regular expressions. – Raphael Jun 10 '14 at 5:26

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$

-

Lazy solution, 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.

-

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

Something like that, not very rigid, may be wrong, but I am in a haste.

-