# How to determine whether this language is regular?

I've encountered this question recently: Given $$\Sigma=\{\sigma_1, \sigma_2, ..., \sigma_n\}$$ and $$n\ge 2$$, determine whether the following language is regular or not: $$L_1=\{w\in\Sigma^*|for \ 1 \le i \le n, \ \#_{\sigma_i}(w) \ is \ even \iff i \ is \ even \}$$ And I need to use the Myhill-Nerode theorem to solve it. I tried constructing a finite automata that accepts this language but had some troubles with it. I'd really appreciate some help!

• I think the condition should be "for all $1 \leq i \leq n$, $\#_{\sigma_i}(w)$ even $\iff$ $i$ even", right? Otherwise it would be the empty language. Edit: For the sake of readability, the $\sigma$ contains $i$ instead of 1 as subscript. Jul 26, 2021 at 15:51
• This problem can be solved without constructing an automaton, so where are your problems? Understanding the language, or understanding Myhill-Nerode? Jul 26, 2021 at 17:07

## 1 Answer

For $$x = (x_1, \dots, x_n) \in \{0,1\}^n$$, define $$C_x = \{ w \in \Sigma^* \mid \forall i=1,\dots,n, \;\; \#_{\sigma_i}(w) \equiv x_i \pmod{2} \}$$. Notice that the collection $$\mathcal{C} = \{C_x \mid x \in \{0,1\}^n\}$$ is a partition of $$\Sigma^*$$ and that $$|C| = 2^n$$.

Let $$\rho \subseteq \Sigma^* \times \Sigma^*$$ be the equivalence relation "having no distinguishing extension" (see the Myhill-Nerode theorem for a definition of "distinguishing extension"). I claim that the quotient set of $$\Sigma^*$$ by $$\rho$$ is exactly $$\mathcal{C}$$. By the Myhill-Nerode theorem, this immediately implies that $$L_1$$ is regular since $$\mathcal{C}$$ is a finite set.

To see that the claim is true, let $$w,w' \in C_x$$ for some $$x \in \{0,1\}^n$$. For any $$z \in \Sigma^*$$ and any $$i=1,\dots,n$$ we have that $$\#_{\sigma_i}(wz) \equiv x_i + \#_{\sigma_i}(z) \equiv x_i + \#_{\sigma_i}(z) \equiv \#_{\sigma_i}(w'z) \pmod{2},$$

showing that either both $$wz$$ and $$w'z$$ belong to $$L_1$$ or neither does. This means that there exists no distinguishing extension for $$w$$ and $$w'$$, i.e., $$w$$ and $$w'$$ lie in the same equivalence class.

Conversely, let $$w \in C_x$$ and $$w' \in C_y$$ for some $$x,y \in \{0,1\}^n$$ with $$x \neq y$$. Let $$j$$ be any index such that $$x_j \neq y_j$$. We construct a distinguishing extension $$z$$ for $$w$$ and $$w'$$ as follows: $$z= \sigma_1^{1-x_1}\,\sigma_2^{x_2}\,\sigma_3^{1-x_3}\,\sigma_4^{x_4}\,\dots$$

By construction $$wz \in L_1$$. Moreover, $$w'z \not\in L_1$$ since we must have: $$\#_{\sigma_j}(wz) \equiv x_j + \#_{\sigma_j}(z) \not\equiv y_j + \#_{\sigma_j}(z) \equiv \#_{\sigma_j}(w'z) \pmod{2}.$$ This shows that $$w$$ and $$w'$$ belong to different equivalence classes and concludes the proof.