2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @plop So that was my initial idea, but I got stuck - maybe incorrectly - at what happens when you look at how the strings in $S_1, ..., S_n$ behave. Why does the fact that two strings $x$ and $y$ end up in the same state $q$ imply that $uxv$ and $uyv$ always end in the same state? (My intuition says that this isn't obvious, but perhaps I'm missing something?) $\endgroup$ – templatetypedef Sep 3 at 0:41
  • $\begingroup$ No, it is I who made a mistake. $\endgroup$ – plop Sep 3 at 0:49
2
$\begingroup$

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 &\iff 1 \cdot xuy \in F \iff ((1 \cdot x) \cdot u) \cdot y \in F \\ &\iff ((1 \cdot x) \cdot v) \cdot y \in F \iff 1 \cdot xvy \in F \\ &\iff xvy \in L \end{align} and thus $u \equiv_S v$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

After a bit more thought I believe this is indeed true and that I've got a proof of it. The idea is to proceed by contrapositive and instead prove that if $L$ is regular, then $\equiv_S$ has only finitely many equivalence classes.

We can see this by pulling in Brzozowski derivatives. Given the language $L$ and any string $x \in \Sigma^*$, we define the Brzozowski derivative of $L$ with respect to $x$ as

$$\partial_x L = \{ w \in \Sigma^* | xw \in L \}$$

With this notation, we see that $uxv \in L$ is equivalent to saying that $xv \in \partial_u L$. This means that we can rewrite the definition of $\equiv_S$ as

$$x \equiv_S y \Leftrightarrow \forall u \in \Sigma^*. \forall v \in \Sigma^*. (xv \in \partial_u L \leftrightarrow yv \in \partial_u L).$$

But that inner part is the definition of Myhill congruence for the language $\partial_u L$, which we'll denote as $\equiv_{M({\partial_u L})}$. Therefore, we see that

$$x \equiv_S y \Leftrightarrow \forall u \in \Sigma^*. x \equiv_{M({\partial_u L})} y$$

A few fun facts about Brzozowski derivatives:

  1. For any language $L$ we have $x \equiv_{M(L)} y$ if and only if $\partial_x L = \partial_y L$. This follows from the definitions - $xw \in L$ means the same as $w \in \partial_x L$.
  2. As a corollary, any regular language has a finite number of distinct Brzozowski derivatives.
  3. The derivative of a regular language is regular - you can just change the start state to the state reached by $x$ to form a DFA for $\partial_x L$ from a DFA for $L$.
  4. As a corollary, $\equiv_{M({\partial_u L})}$ has only finitely many equivalence classes for any string $u$.

So overall, we see that $x \equiv_S y$ means that $x$ and $y$ are Myhill-equivalent for each of the (finitely many) distinct Brzozowksi derivatives of the original language. There are only finitely many combinations of a derivative and a Myhill equivalence class of the derivative, so there are only finitely many equivalence classes for $\equiv_S$.

There is almost certainly a better way to prove this, but this is just the one I came up with. Please let me know if I missed anything or if this is incorrect!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think it is ok. Another way to say the same is to look at the partitions $P_1,P_2,...,P_n$ of the words, in which $P_i=\{S_{i,1},S_{i,2},...,S_{i,n}\}$ and $S_{i,j}$ are the words that would make the DFA end in state $j$ if input when the DFA is on state $i$. The $P_i$ are finitely many, and consist of finitely many elements each. The meet of these partitions (the largest partition that refines all of them) is also finite, since it consists of the non-empty sets that are intersections of $\bigcap_{i=1}^{n}A_i$ with $A_i\in P_i$. Call the elements of the meet $Q_1,Q_2,...,Q_m$. $\endgroup$ – plop Sep 3 at 2:01
  • $\begingroup$ If $x,y\in Q_k$, then $x\equiv_S y$, because no matter in which state the DFA starts, if $x$ and $y$ are input, then they make the DFA end in the same state. Therefore, the equivalence classes of $\equiv_S$ are unions of some $Q_k$ and therefore there are only finitely many of them. Incidentally we have that $m\leq n^n$, by counting what would be the maximum number of different intersections $\bigcap_{i=1}^{n}A_i$ we could possibly form. Therefore, the number of equivalence classes of $\equiv_S$ is also $\leq n^n$. $\endgroup$ – plop Sep 3 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.