2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Klaus Draeger Jun 9 '14 at 16:55
7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

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