Myhill-Nerode and closure properties

Question

It is well known that regular languages are characterized by the Myhill-Nerode equivalence. For language $L$ over $\Sigma^*$ define the equivalence $x\sim_L y$ over $\Sigma^*$ iff for all $z\in\Sigma^*$ we have $xz\in L \iff yz\in L$. Then $L$ is regular iff $\sim_L$ is of finite index, i.e., has a finite number of equivalence classes.

I know that the relation can be used to show that some languages are not regular, by indicating infinitely many strings that are not equivalent.

My question: can we easily use Myhill-Nerode to show closure properties of regular languages? Or should we use the "syntactic congruence" of languages?

As an example for prefix it is easy, as $x\sim_L y$ implies $x\sim_{\mbox{pref}(L)} y$. But how do we handle suffix, concatenation, star, mirror?

Answer 1

I do closure under boolean operations with the MyHill-Nerode characterisation. Never saw it done that way. A right congruence $\sim$ saturates a language $L$ if $$ u \sim v \Rightarrow ( u \in L \leftrightarrow v \in L ) $$ or equivalently iff $L$ is an union of congruence classes. We use:

Theorem: (MyHill-Nerode) A language is regular if and only if there is a right-congruence of finite index that saturates $L$.

Now suppose we have regular languages $L_1, L_2 \subseteq X^{\ast}$, and denote $\sim_{L_1}, \sim_{L_2}$ some right congruences of finite index saturating them. Then $$ u \sim v :\Leftrightarrow u \sim_{L_1} v \land u \sim_{L_2} v $$ is a right congruence (the intersection of both), and it refines both. Furthermore we have $$ [u]_{\sim} = [u]_{\sim_{L_1}} \cap [u]_{\sim_{L_2}}. $$ Hence we have a finite number of equivalence classes. Also this gives that the intersection of equivalence classes $[u]_{\sim_{L_1}}$ and $[v]_{\sim_{L_2}}$ is either empty, or it has a common element $w$ and hence equals the equivalence class $[w]_{\sim}$. This gives that $L_1 \cap L_2$ is either empty or could be written as the union of equivalence class for $\sim$. By the above theorem $L_1 \cap L_2$ is regular.

For $L_1 \cup L_2$ it is an union of equivalence classes for $\sim_1$ and $\sim_2$, which are themselve unions of equivalence classes for $\sim$, hence it is also regular. And for complementation, this follows as the equivalence classes partition $X^{\ast}$, hence a right congruence working for $L_1$ works also for $X^{\ast} \setminus L_1$. $\square$

Additional comments: In your question you also mentioned the canonical Nerode right congruence $$ u \equiv_L v :\Leftrightarrow (\forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L) $$ with $L \subseteq X^{\ast}$. This is the coarsest right-congruence saturating $L$. Now maybe it might be natural to ask if we can construct the Nerode right congruence of $L_1 \cap L_2$ or $L_1 \cup L_2$ easily out of the ones for $L_1, L_2$, or if the resulting intersection congruence arises as some Nerode right congruence. Maybe we can find such simple formulas like $$ u \equiv_{L_1\cap L_2} v \Leftrightarrow u \equiv_{L_1} v \land u \equiv_{L_2} v. $$ But the above does not hold. And to my knowledge there does not exists any simple relation. For example consider $L_1 = (aa)^{\ast}$ and $L_2 = a(aa)^+$, then we have $$ L_1 \cap L_2 = \emptyset, \qquad L_1 \cup L_2 = X^{\ast} \setminus \{a\}. $$ Now $\equiv_{L_1} \cap \equiv_{L_2}$ has at least four congruence classes, as it refines $\equiv_{L_2}$ which has exactly four congruence classes. But $\emptyset$ has precisely one class, and $X^{\ast} \setminus \{a\}$ has three (could all be easily seen by using minimal complete automata).

EDIT (2019.08.18). The mirror and suffix operation are related to the left congruence $$ u \equiv^L v \Leftrightarrow \forall w \in X^* : wu \in L \leftrightarrow wv \in L. $$ If $\equiv^L$ has finite index, similar as for the prefix-operation and the right-congruence, $\equiv^{\operatorname{suffix}(L)}$ has finite index. And $u \equiv_L v$ iff $\operatorname{mirror}(u) \equiv^{\operatorname{mirror}(L)} \operatorname{mirror}(v)$; and as the mirror operation is a bijection on $X^*$ the last equation gives that $\equiv^{\operatorname{mirror}(L)}$ has finite index iff $\equiv_L$ has finite index (note that the left congruence has the same index as the right congruence for the mirrored words, but in general a right congruence for $\operatorname{mirror}(L)$ might have exponential many more classes as is shown by standard contructions from automata theory).

So these operations are handled if we can show that both congruences have finite index at the same time or not. For this lets look at the syntactic congruence $$ u \equiv_{S(L)} v \Leftrightarrow \forall x,y \in X^* : xuy \in L \Leftrightarrow xvy \in L. $$ This congruence refines both congruences above, hence if it is finite, both congruence above are also finite. It is $u \equiv_{S(L)} v$ iff for all $w \in X^*$ we have $[wu]_{\equiv_L} = [wv]_{\equiv_L}$, hence we have a well-defined and injective map from the $\equiv_{S(L)}$-equivalence classes to the transformations on $\{ [w]_{\equiv_L} : w \in X^* \}$, and if the latter is a finite set, the set of those transformations is finite too, which implies that $\equiv_{S(L)}$ is of finite index. So in total we have that $\equiv^L$ has finite index if $\equiv_L$ has finite index, the reverse is implied similar.

Answer 2

The equivalence classes of the Myhill-Nerode relation are also the states of the minimal DFA for the language. So whatever is easy to show using DFAs, you can convert to a proof which uses the Myhill-Nerode point of view. Wherever you need NFAs, you can expect the proof to get more complicated.

But the correct answer is: try it out for yourself! That's how research is done.