# Proving regularity via equivalence classes

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?

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.

• "Taking suffixes and prefixes is a closure property of regular languages" can you elaborate on that? This was proven to us, or at least not in the way you are using it here. Dec 17, 2012 at 19:21
• OK, I tried to be more explicit. I am not certain whether these are the points you needed elaboration. Dec 17, 2012 at 23:54
• @HendrikJan : Hi Hendrik!..+1 to your answer, I request you please check my answer too Dec 18, 2012 at 10:46
• @HendrikJan What does mean by rank(L) here? Dec 18, 2012 at 12:59
• @GrijeshChauhan: ah, question also posted elsewhere! (where I do not have an account...). I believe rank(L) might be the number of equivalence classes for L. This number is finite iff the language is regular. That confuses me: according to the question we must use equivalence classes, but we cannot use the number of classes. Dec 18, 2012 at 23:11

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

Lsuff = { w1 | xw1 ∈ L1 }
Lpref = { w2 | w2y ∈ L2 }

And,

L = LsuffLpref

We can easily proof by construction Finite Automata for L.

Suppose Finite Automata(FA) for L1 is M1 and FA for L2 is M2.

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

e.g.
L1 = {ab ,ac} and L2 = {12, 13}

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

M1 =is consist of Q = {q0,q1,qf} with edges:

q0 ---a----->q1,
q1 ---b/c--->qf

Similarly :

M2 =is consist of Q = {p0,p1,pf} with edges:

p0 ---1----->p1,
p1 ---2/3--->pf

Now, NFA for L called M will be consist of Q = {q0,q1,qf, p0,p1,pf} Where Final state of M is pf and edges are:

q0 ---a----->q1,
q1 ---b/c--->qf,
p0 ---1----->p1,
p1 ---2/3--->pf,

q0 ----^----> p0,
q1 ----^----> p0,
qf ----^----> p0,

q0 ----^----> p1,
q1 ----^----> p1,
qf ----^----> p1,

q0 ----^----> pf,
q1 ----^----> pf,
qf ----^----> pf

^ means NULL-Transition.

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