1
$\begingroup$

Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?

Thank you for any input.

$\endgroup$
1
$\begingroup$

The most direct method to solve the problem is to show to build, starting with finite state automata $A_L$ and $A_M$ for the regular languages $L,M$, a new automaton for the new language $K$ which is constructed from $L$ and $M$.

For this you need an idea, a formal construction, and (if you are not convinced) a proof the construction is correct.

The idea can be as follows. If the automaton $A_L$ follows a path on a word, one should be able to decompose this in the form $uvw$ in such a way that the subword $v$ can be accepted by $A_M$. The middle part $v$ should be made invisible in the new automaton for $K$. This idea can be made formal using concepts from finite automata like $\varepsilon$-instructions and direct product construction.

If you have knowledge of other closure properties then the one from this exercise can be deduced. Closure properties you then need are intersection, morphism and inverse morphism.

Enjoy.

$\endgroup$
1
  • $\begingroup$ For an (unrelated) question, Yuval writes a detailed contruction that builds a new automaton from two given ones. The languages operation is similar, but NOT identical. $\endgroup$ – Hendrik Jan May 16 '20 at 15:11
1
$\begingroup$

Yes $K$ is a regular language. Lets try to see this using closure properties of regular languages. Consider the marked duplicate alphabet of $\Sigma$, $\Sigma' = \{ a' | a \in \Sigma \} $. Now consider the homomorphisms $\alpha, \beta, \gamma$ defined as follows. $$ \alpha : \Sigma \cup \Sigma' \mapsto \Sigma$$ $$ \alpha(a) = a $$ $$\alpha(a') = a$$

$$ \beta : \Sigma \cup \Sigma' \mapsto \Sigma$$ $$ \beta(a) = a $$ $$\beta(a') = \epsilon$$

$$ \gamma : \Sigma \mapsto \Sigma'$$ $$ \gamma(a) = a'$$ Then $$ K = \beta(\Sigma^*\gamma(M)\Sigma^* \cap \alpha^{-1}(L)) $$

Since regular languages are closed under morphisms and inverse morphisms $K$ is also regular

$\endgroup$

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.