Find the languages that can represent the equivalence classes

61 Views Asked by At

Assume $\Sigma = \{a,b\}$ and $L$ is a language over $\Sigma$ for which $R_L$ has the following three equivalence classes: $\{\lambda\}$, the set of all odd-length words, and the set of all non-empty even-length words.

Why couldn't $L = \{x \mid |x|\text{ is odd}\}$? (Hint: Recompute $R\{x \mid |x|\text{ is odd}\}$.)

List the languages $L$ that could give rise to this $R_L$

$R$ stands for relation.

1

There are 1 best solutions below

0
On

HINT: If $L$ is the set of words over $\Sigma$ of odd length, then $R_L$ has only two equivalence classes: $x\mathrel{R_L}y$ if and only if $|x|\equiv|y|\pmod2$, so the $R_L$-equivalence classes are $\{x\in\Sigma^*:|x|\text{ is even}\}$ and $\{x\in\Sigma^*:|x|\text{ is odd}\}=L$. This doesn’t meet the requirements, because it doesn’t split off the empty word into a class of its own.

Taking $L$ to be the set of words over $\Sigma$ of even length has the same problem, but what if we let $L$ be the set of non-empty words of even length?

  • If $x,y\in\Sigma^*$ are both of odd length, then for any $z\in\Sigma^*$ either $|z|$ is even, in which case $|xz|$ and $|yz|$ are both odd, or $|z|$ is odd, in which case $|xz|$ and $|yz|$ are both even and positive.

  • If $x,y\in\Sigma^*$ are both of positive even length, then for any $z\in\Sigma^*$ either $|z|$ is even, in which case $|xz|$ and $|yz|$ are both even and positive, or $|z|$ is odd, in which case $|xz|$ and $|yz|$ are both odd.

  • If $x,y\in\Sigma^*$, $|x|$ is odd, and $|y|$ is even and positive, then $x\not\mathrel{R_L}y$; why?

  • If $\lambda\ne x\in\Sigma^*$, then $\lambda\not\mathrel{R_L}x$; why?

It follows that $R_L$ has the desired equivalence classes. The only question now is whether there is any other language $L'$ such that $R_{L'}$ has the same equivalence classes.

Let $C_0=\{\lambda\}$, $C_1=\{x\in\Sigma^*:|x|\text{ is odd}\}$, and $C_2=\{x\in\Sigma^*\setminus\{\lambda\}:|x|\text{ is even}\}$. The proof of the Myhill-Nerode theorem shows that if $L$ is any language such that $R_L$ has these three equivalence classes, there is a DFA that recognizes $L$ and has states $q_0,q_1$, and $q_2$ and the following transition table:

$$\begin{array}{c|cc} \text{state}\backslash\text{input}&a&b\\ \hline q_0&q_1&q_1\\ q_1&q_2&q_2\\ q_2&q_1&q_1 \end{array}$$

Moreover, this DFA is minimal, in the sense that no DFA with fewer states recognizes $L$. The idea is that the DFA is in state $q_k$ when the input so far is a word in class $C_k$; check that the transition table matches this idea.

  • Which state must be the initial state in order for the DFA to match that idea?

Since the state set, input alphabet, initial state, and transition function are completely determined by the desired equivalence classes, the only thing that can vary is the set of acceptor (final) states. If $q_2$ is the only acceptor state, the DFA recognizes the language $C_2$ of words over $\Sigma$ of positive even length. If $q_1$ is the only acceptor state, the DFA recognizes $C_1$, but there is a DFA with only two states that recognizes $C_1$, since we can collapse $q_0$ and $q_2$ into a single state. Our $3$-state DFA that recognizes $C_1$ isn’t minimal, so — as we saw directly in the first paragraph — $R_{C_1}$ has only two equivalence classes, and $C_1$ is not one of the languages for which we’re looking.

  • In principle any subset of $\{q_0,q_1,q_2\}$ can be the set of acceptor states of the DFA. We’ve seen what happens when we choose the sets $\{q_1\}$ and $\{q_2\}$; check the other six subsets of $\{q_0,q_1,q_2\}$ to see whether making any of them the set of acceptor states makes the DFA recognize a language $L$ such that $R_L$ has the equivalence classes $C_0,C_1$, and $C_2$.