The Problem
Let $\Sigma = \left\{a,b,c\right\}$ and $L = \left\{ wcw \ |\ w \in \left\{a,b\right\}^* \right\}$
Additionally, define for $v,w \in \Sigma^*$: $$v \approx_L w \Longleftrightarrow \forall z \in \Sigma^*: wz \in L \Leftrightarrow vz \in L$$
What are the equivalence classes $EC(\approx_L)$ into which $\approx_L$ partitions $\Sigma^*$?
My idea
As per usual, my idea is fairly complicated. I've attempted to check various cases for words $w,v \in \Sigma^*$ to see under which circumstances they are equivalent or not equivalent. To keep it short, here's a list of my findings. Note that $\#_c(w)$ refers to the count of $c$s in a given word $w$, $\varepsilon$ is the empty word, and $\dot\lor$ means the external or:
- Case 1: $\#_c(w) = \#_c(v) = 0 \Longrightarrow w \not\approx_L v$ $\qquad$ $wz \in L \Leftrightarrow z=cw$
- Case 2: $\#_c(w) \geq 2 \land \#_c(v) \geq 2 \Longrightarrow w \approx_L v$ $\qquad$ $\forall z \in \Sigma^*: wz,vz \notin L $
- Case 3: $\#_c(w) = \#_c(v) = 1 \land w,v \in L_2 \Longrightarrow w \approx_L v$ $\qquad$ $wz,vz \in L \Leftrightarrow z=\varepsilon$
- Case 4: $\#_c(w) = \#_c(v) = 1 \land w,v \notin L_2$. Then let $w = x_wcy_w, v = x_vcy_v$
- Case 4.1: $y_w$ not prefix of $x_w$ and $y_v$ not prefix of $x_v$ $\Longrightarrow$ $w \approx_L v$ $\quad$ $\forall z \in \Sigma^*: wz,vz \notin L$
- Case 4.2: $y_w$ prefix of $x_w$ and $y_v$ not prefix of $x_v$ $\Longrightarrow$ $w \not\approx_L v$ $\qquad$ $wz \in L \Leftrightarrow x_w = y_zz$
- Case 4.3: $y_w$ prefix of $x_w$ and $y_v$ prefix of $x_v$ $\qquad$ $wz \in L \Leftrightarrow x_w = y_zz$
- Case 4.3.1: $y_w \neq y_v\ \dot\lor\ x_w \neq x_v$ $\Longrightarrow$ $w \not\approx_L v$
- Case 4.3.2: $y_w \neq y_v \land x_w \neq x_v$: Can't easily determine. We have $w \approx_L v \Longleftrightarrow x_v = y_v.z$ for a $z$ defined by $x_w = y_wz$.
Now as you can see, this idea is quite complex and still doesn't provide the complete solution. Combining case 2 and 4.1, and utilizing case 1 and 3 I find that the following are equivalence classes of $\approx_L$: $$ \left\{w \in \Sigma^*\ |\ \#_c(w) \geq 2 \right\} \cup \left\{x_wcy_w\ |\ x_w,y_w \in \left\{a,b\right\}^* y_w \text{ not prefix of } x_w \right\} $$ $$ \text{All } \left\{w \in \Sigma^*\right\} \text{ where } \#_c(w) = 0 $$ $$ \text{All } \left\{ w \in L \right\} $$
This however doesn't utilize the findings of Cases 4.2, 4.3.1 and 4.3.2. Do you see a way to continue my attempts?
Or even better, do you see an easy solution to this problem?