Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $L_{1,}L_{2}$ be regular languages and define $L:=\{uw \mid \exists v\in\Sigma^{*}:uv\in L_{1},vw\in L_{2}\}$.

I wish to prove that $L$ is regular using only closure properties (such as $L_{1},L_{2}$ is regular then so is $L_{1}\cap L_{2},L1\cup L_{2},L_{1}^{*}$ etc.).

My thoughts: I tried to define a homomorphism $h:\Sigma\cup\Sigma'\to\Sigma^{*}$

$$\forall\sigma\in\Sigma:h(\sigma)=\sigma$$ $$\forall\sigma'\in\Sigma':h(\sigma')=\epsilon$$

Then I tried to look at $h^{-1}(L_{1}),h^{-1}(L_{2})$, I thought about looking at their intersection with the languages $\Sigma^{*}(\Sigma')^{*},(\Sigma')^{*}\Sigma^{*}$ etc to give the words in $h^{-1}(L_{1}),h^{-1}(L_{2})$ the form of $ww'$s.t $w\in L_{1}$ or $w'w$ s.t $w\in L_{2}$.

I am having difficulty to continue, I thought about trying to get to something like $L_{3}(\Sigma')^{*}L_{4}$ where $L_{3}$ is all the prefix of words in $L_{1}$ and $L_{4}$ is all the endings of words in $L_{2}$ and then intersect this with $\Sigma^{*}L_{5}'\Sigma^{*}$ where $L_{5}$ is some language to enforce that the words in $(\Sigma')^{*}$in the expression$L_{3}(\Sigma')^{*}L_{4}$ will be such that if I remove all the tags (using a homomorphism) I would get $L$.

How can I show $L$ is regular using only closure properties ?

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

Let $\underline \Sigma := \{ \underline a : a \in \Sigma \}$ be a disjoint copy of $\Sigma$, assume $<$ and $>$ are symbols not already present in $\Sigma$ and define a homomorphism $h: \Sigma \cup \underline \Sigma \cup \{<,>\} \to \Sigma$ by \begin{align*} a &\mapsto a,\\ \underline a &\mapsto a,\\ < &\mapsto \varepsilon,\\ > &\mapsto \varepsilon.\\ \end{align*} Then \begin{align*} K &:= \{ u \text{<}\underline v \text{>} w : uv \in L_1, vw \in L_2 \}\\ &= \Sigma^* \text{<}\underline{\Sigma}^*\text{>} \Sigma^* \cap h^{-1}(L_1)\text{>}\Sigma^* \cap \Sigma^* \text{<}h^{-1}(L_2) \end{align*} is regular by the closure properties of regular languages, and so is $L$ since it is the homomorphic image of $K$ by deleting the symbols from $\underline \Sigma$ and $\{<,>\}$.

share|improve this answer
    
Can you please explain the last equality ? I understand the first set in the intersection but not the other two (that is, I don't understand how intersecting with the second and third set gives you the conditions $uv\in L_1$ and $vw\in L_2$ ) –  Belgi Aug 22 '12 at 11:36
    
The first set makes sure that the word is of the form $u\text{<}\underline{v}\text{>}w$. The intersection with the second set says that the word must also be of the form "something in $h^{-1}(L_1)$ followed by a $>$ symbol and some word from $\Sigma^*$". Since there is exactly one occurrence of the $>$ symbol the $h^{-1}(L_1)$ part has to be $u\text{<}\underline{v}$, so we demand that $h(u\text{<}\underline{v}) = uv$ is in $L_1$. The third set similarly makes sure that $vw \in L_2$. –  marlu Aug 22 '12 at 11:44
    
but the symbol $<$ should follow the word in $h^{-1}(L_1)$ not $>$...am I understanding this wrong ? –  Belgi Aug 22 '12 at 11:47
    
No, the $h^{-1}(L_1)$ part should be followed by $>$. The word $u\text{<}\underline{v}\text{>}w$ is decomposed as $u\text{<}\underline{v} \circ \text{>} \circ w$ where the first part must be in $h^{-1}(L_1)$. –  marlu Aug 22 '12 at 12:55
add comment

Another way is to make 3 distinct copies $\Sigma_i$ of $\Sigma$, and define the morphisms $h_i : \Sigma_1 \cup \Sigma_2 \cup \Sigma_3 \to \Sigma^*$, by $a_i \mapsto \varepsilon ; a_j \mapsto a$ for $j \neq i$ ($h_i$ simply erases the letters from $\Sigma_i$)

Then $L = h_2(\Sigma_1^* \Sigma_2^* \Sigma_3^* \cap h_3^{-1}(L_1) \cap h_1^{-1}(L_2))$

share|improve this answer
add comment

There is a simple solution using Nerode's theorem. Given a language $L$ and a word $u$, the left [right] quotient of $L$ by $u$ are defined by $u^{-1}L = \{v \mid uv \in L\}$ and $Lu^{-1} = \{v \mid vu \in L\}$.

Nerode's theorem states that a language is regular if and only if it as finitely many left (respectively right) quotients. Further, the quotients of a regular language are also regular. That being said, your language is equal to $$ L = \bigcup_{v \in A^*} (L_1v^{-1})(v^{-1}L_2) $$ and since $L_1$ and $L_2$ are regular, this apparently infinite union can be rewritten as a finite union. To be precise, there are only finitely many pairs of the form $(L_1v^{-1},v^{-1}L_2)$. Thus $L$ is regular.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.