Proving non-regularity via syntactic congruence classes? Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation:
$$x \equiv_M y \Leftrightarrow \forall v \in \Sigma^*. (xv \in L \leftrightarrow yv \in L).$$
One corollary of the Myhill-Nerode theorem is that if $\equiv_M$ has infinitely many equivalence classes, then $L$ is not a regular language.
There's a different equivalence relation called syntactic congruence which is also due to Myhill:
$$x \equiv_S y \Leftrightarrow \forall u \in \Sigma^*. \forall v \in \Sigma^*. (uxv \in L \leftrightarrow uyv \in L).$$
My question is the following: is it also the case that if $\equiv_S$ has infinitely many equivalence classes, then $L$ is not a regular language? I've tried a smattering of regular languages and each one I've tried has a finite number of these equivalence classes, but I don't see a way to get a general proof to that effect (and I'm not even sure one exists!)
You want to prove that if $\equiv_S$ has infinite index, then $L$ is not a regular language, or, equivalently that if $L$ is regular, then $\equiv_S$ has finite index. This is an immediate consequence of the following result.
Theorem. Let ${\cal A} = (Q, \Sigma, \cdot, i, F)$ be the minimal complete deterministic automaton of $L$. Then $u \equiv_S v$ if and only if, for every state $q \in Q$, $q \cdot u = q \cdot v$.
Proof. Suppose that $u \equiv_S v$ and let $q \in Q$. Since $\cal A$ is minimal, it is accessible, and there exists a word $x$ such that $i \cdot x = q$. Now, for every word $y$,
$$
xuy \in L \iff xvy \in L, 
$$
or, equivalently,
$$
1 \cdot xuy \in F \iff 1 \cdot xvy \in F
$$
that is,
$$
(q \cdot u) \cdot y \in F \iff (q \cdot v) \cdot y \in F
$$
It follows that the states $q \cdot u$ and $q \cdot v$ are equivalent, and hence equal, since $\cal A$ is minimal.
Suppose now that for every state $q \in Q$, $q \cdot u = q \cdot v$. Let $x$ and $y$ be words. Then the following equivalences hold:
\begin{align}
xuy \in L &amp;\iff 1 \cdot xuy \in F \iff ((1 \cdot x) \cdot u) \cdot y \in F \\
&amp;\iff ((1 \cdot x) \cdot v) \cdot y \in F \iff 1 \cdot xvy \in F \\
&amp;\iff xvy \in L
\end{align}
and thus $u \equiv_S v$.