0

Question: Define the following operation: $$\text{SubString}(L_1, L_2) = \{w \mid \exists x, y \in L_1, xwy \in L_2\}$$ Let $L_1$ be any language, and $L_2$ regular. Prove that $\text{SubString}(L_1, L_2)$ is regular.

Thoughts:

I need to somehow add states to $M(L_2)$. I thought of a start:

  1. Add an epsilon move from each $q$ s.t. $x$ reaches that $q$ on $M$ to $q_0$ (start state) of $M$. Make each of these $q$'s an accepting state.

  2. Add an epsilon move from each $q\in F(M)$ to $q_0$, remove these $q$'s from the accepting states group of the new NFA.

So what happens is that the NFA now reads $x$ - gets to some marked $q$, goes to the start, reads $w$, goes to the start, reads $y$ and accepts if $y$ gets to some marked $q$.

Since we built an NFA for it, substring is a regular language.

Is this solution correct?

J.-E. Pin
  • 40,163
jreing
  • 3,297

2 Answers2

1

I can't completely follow your construction, I think the details aren't correct, but the general idea is.

Assume we have an automaton for $L_2$ with start state $q_0$ and halting states $F$.

Let $S$ be the set of states that can be reached starting from $q_0$ with a word in $L_1$.

Let $F'$ be the set of states from which a halting state can be reached with a word in $L_1$.

Note that these are well-defined sets, no matter how $L_1$ is given. The worst that could happen is that we can't compute them, but we only care about their existence.

Now an automaton accepting the substring language can be given by modifying the automaton for $L_2$. We add one new state $q_{00}$ and $\varepsilon$-transitions from it to every state in $S$. We let $q_{00}$ be the new start state, and $F'$ the new set of halting states.

If this automaton accepts a word $w$, it first uses one $\varepsilon$-transition corresponing to a word $x\in L_1$, then uses the same transitions as the old automaton would have used, ending in a state in $F'$ for which there exists a word $y\in L_1$ that leads to a state in $F$. So the word $xwy$ is accepted by the old automaton, so it belongs to $L_2$, so $w$ indeed belongs to the substring language.

For the other direction, let $w$ belong to the substring language, so there are $x,y\in L_1$ such that $xwy\in L_2$. The state the old automaton reaches from $q_0$ with input $x$ is in $S$, so the new automaton has an $\varepsilon$-transition to it from its starting state. From this state, both automata reach the same state $q$ with input $w$. Since $xwy\in L_2$, the old automaton reaches a state in $F$ from $q$ with input $y$, so that $q\in F'$ and $w$ is accepted by the new automaton.

So the new automaton accepts the substring language, which is therefore regular.

Christian Sievers
  • 1,069
0

You don't need automata to solve this question. Given a language $L$ and two words $x, y \in A^*$, let $$ x^{-1}Ly^{-1} = \{ u \in A^* \mid xuy \in L \} $$ By Nerode's lemma, if $L$ is a regular language, there are only finitely many languages of the form $x^{-1}Ly^{-1}$, all of which are regular. Now, your language can be written as $$ \text{SubString}(L_1, L_2) = \bigcup_{x, y \in L_1} x^{-1}L_2y^{-1} $$ Thus $\text{SubString}(L_1, L_2)$ is a finite union of regular languages and hence is regular.

J.-E. Pin
  • 40,163