Proving regularity via equivalence classes

Question

Given two regular languages $L_1$ and $L_2$, we define a new language

$$L=\{w_1w_2\mid \text{ there exist two words } x,y \text{ such that } xw_1\in L_1, w_2y\in L2\}$$

How do I show that $L$ is regular with equivalence classes?

My assignment allows the use of closure properties that all regular languages hold, but I cannot use $\text{rank} (L)$, as in show a limit to the number of equivalence class.

Can someone lead me in the right direction?

Answer 1

If you are allowed to use closure properties (as the formulation in the question suggests) then $xw_1\in L_1$ so $w_1$ is a suffix of $L_1$, similarly $w_2$ is a prefix of $L_2$. Taking suffixes and prefixes is a closure property of regular languages, and so is concatenation. That solves the regularity.

At what level do you want/need equivalence classes for your answer?

(added) For language $K$ its set of prefixes is defined as $$\mbox{pref}(K) = \{ w \mid \mbox{there exists string $y$ such that } wy\in K \}$$ precisely as used for $L_2$ in the operation in the question.

Given a finite state automaton for $K$ we get a FSA for $\mbox{pref}(K)$ by making all states final that have a path leading to a final state.

Also $\mbox{suff}(K) = \{ w \mid \mbox{there exists string $x$ such that } xw\in K \}$. Similarly one proves closure under suffix by making all states initial. As that is not commonly allowed for FSA that is solved by adding $\varepsilon$-transitions to all other states.

Your language $L$ based on $L_1,L_2$ equals $\mbox{suff}(L_1)\mbox{pref}(L_2)$, the concatenation of a suffix and a prefix language.

I could not find a reference to a question in this forum that dealt with the prefix/suffix operations, perhaps someone can help. Closure under prefix is a special case of closure under quotient.

Answer 2

L = {w1w2| there are two words, x,y such that : xw1 is in L1, w2y is in L2} is regular if L₁ and L₂ are regular languages.

L_suff = { w₁ | xw₁ ∈ L₁ }
L_pref = { w₂ | w₂y ∈ L₂ }

And,

L = L_suffL_pref

We can easily proof by construction Finite Automata for L.

Suppose Finite Automata(FA) for L₁ is M₁ and FA for L₂ is M₂.

[SOLUTION]
Non-Deterministic Finite Automata(NFA) for L can be drawn by introducing NULL-transition (^-edge) form every state in M₁ to every state in M₂. then NFA can be converted into DFA.

e.g.
L₁ = {ab ,ac} and L₂ = {12, 13}

L = {ab, ac, 12, 13, a12, a2, ab12, ab2, a13, a3, ab13, ab3, ............}
Note: w₁ and w₂ can be NULL

M₁ =is consist of Q = {q₀,q₁,q_f} with edges:

q₀ ---a----->q₁,
q₁ ---b/c--->q_f

Similarly :

M₂ =is consist of Q = {p₀,p₁,p_f} with edges:

p₀ ---1----->p₁,
p₁ ---2/3--->p_f

Now, NFA for L called M will be consist of Q = {q₀,q₁,q_f, p₀,p₁,p_f} Where Final state of M is p_f and edges are:

q₀ ---a----->q₁,
q₁ ---b/c--->q_f,
p₀ ---1----->p₁,
p₁ ---2/3--->p_f,

q₀ ----^----> p₀,
q₁ ----^----> p₀,
q_f ----^----> p₀,

q₀ ----^----> p₁,
q₁ ----^----> p₁,
q_f ----^----> p₁,

q₀ ----^----> p_f,
q₁ ----^----> p_f,
q_f ----^----> p_f

^ means NULL-Transition.

Now, A NFA can easily convert into DFA.(I leave it for you)

[ANSWER]
DFA for L is possible hence L is Regular Language.

---

I will highly encourage you to draw DFA/NFA figures, then concept will be clear.