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