0
$\begingroup$

I tried writing a solution for a question that defined a language $L$ and asked to find the equivalence classes of the relation $R_{L}$

The TA wrote that "this is not what you should prove" (or "this is not what should be proven") [in free translation].

I wish to know if I actually gave the correct claims that needs to be proven (I do not ask if their proof is correct, but rather on the logic - are my claims a proof assuming their proof is correct).

These are the steps of my proof:

1) for every $n\in\mathbb{Z}$ I defined $A_{n}$. I believed (and this was marked as correct) that those are the equivalence classes of the relation $R_{L}$ .

I have proved:

2) $\forall n\in\mathbb{Z}:\, A_{n}\neq\emptyset$ (I used it to prove another claim)

3) Let $n\in\mathbb{Z}$and $x,y\in A_{n}$ then $\forall z\in\Sigma^{*}:\, xz\in A_{n}\iff yz\in A_{n}$

4) $x\sim y\iff\exists n\in\mathbb{Z}:\, x,y\in A_{n}$ is an equivalence relation

5) $\forall w\in\Sigma^{*}:\exists n\in\mathbb{Z}:\, w\in A_{n}$

6) $x\sim y\implies xR_{L}y$

7) I concluded that by the above $\sim$ refines $R_{L}$

8) Let $n_{1}\neq n_{2}\in\mathbb{Z},x\in A_{n_{1}},y\in A_{n_{2}}$ then $\exists z\in\Sigma^{*}:xz\in L,yz\not\in L$ .

9) I concluded that all the $A_{n}$ are indeed the equivalence classes of $R_{L}$.

Is there a problem with my logic ? I believe that these steps are correct (in terms that if they are correct I proved that all the $A_{n}$ are indeed the equivalence classes of $R_{L}$) but I got $0$ point (out of $10$).

I would appreciate any help in figuring out if there is anything wrong in the way I have proved the claim!

1 Answers 1

2

Let me make sure that I understand what you did. In (2) you proved that the sets $A_n$ are non-empty. In (4) you proved that they are pairwise disjoint, so that they form a partition of their union, and you defined $\sim$, the corresponding equivalence relation on $\bigcup_nA_n$. In (5) you showed that $\bigcup_nA_n=\Sigma^*$ and hence that $\sim$ is an equivalence relation on $\Sigma^*$. In (6) you proved that the partition $\{A_n:n\in\Bbb N\}$ refines the Myhill-Nerode partition $\mathscr{P}$; (7) just restates this. In (8) you showed that if $x\not\sim y$, then $x(\lnot R_L)y$. Thus, distinct members of $\{A_n:n\in\Bbb N\}$ are contained in distinct members of $\mathscr{P}$, and $\{A_n:n\in\Bbb N\}=\mathscr{P}$. (Equivalently, (6) and (7) combine to give you $x\sim y$ iff $x\,R_L\,y$, and hence $\{A_n:n\in\Bbb N\}=\mathscr{P}$.)

The logic seems fine to me. I assume that (3) was a technical lemma needed to prove one of the significant points above.

  • 0
    @Belgi: I thought that it was probably something like that, but since it didn’t affect the overall logic of the argument, which is all that concerned me, I didn’t worry about the details.2012-10-17