-1
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – ttnick
    Jul 26, 2021 at 15:51
  • 2
    $\begingroup$ This problem can be solved without constructing an automaton, so where are your problems? Understanding the language, or understanding Myhill-Nerode? $\endgroup$ Jul 26, 2021 at 17:07

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.