# 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.

(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. – user5074 Dec 17 '12 at 19:21
• OK, I tried to be more explicit. I am not certain whether these are the points you needed elaboration. – Hendrik Jan Dec 17 '12 at 23:54
• @HendrikJan : Hi Hendrik!..+1 to your answer, I request you please check my answer too – Grijesh Chauhan Dec 18 '12 at 10:46
• @HendrikJan What does mean by rank(L) here? – Grijesh Chauhan Dec 18 '12 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. – Hendrik Jan Dec 18 '12 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)