There is an exercise in Kozen's book on the equivalence classes of a relation: I need to describe the equivalence classes of the relation ☰PAREN, where PAREN is the set of balanced strings of parentheses [ ].
I thought I solved the exercise by following:
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Applying Myhill-Nerode equivalence on strings over Σ induced by A ⊆ Σ*: Let A be a language over Σ. For all x, y ∈ Σ*: x ☰A y ⇔ ∀z ∈ Σ* (x⋅z ∈ A ⇔ y⋅z ∈ A), meaning that the equivalence classes of ☰A are sets of strings that behave equivalently under extension.
In our case, a string x⋅z ∈ PAREN iff z matches(or "closes") all unmatched(or "open") "["-characters, therefore z is a string in (])* that matches all unmatched "[" (left parentheses) - characters of x. All y strings that contain the same number of unmatched left parentheses as x will also match z ⇒ be equivalent to x.
The equivalence classes are:
1) a*[a*, a ∈ PAREN /* one unmatched left parenthesis in the string */
2) a*[[a*, a ∈ PAREN /* two unmatched left parentheses in the string */
3) a*[[[a*, a ∈ PAREN /* three unmatched left parentheses in the string */
...
{there will be infinite number of classes and epsilon-class}
Thus, there is infinite number of equivalence classes, and they are all distinguishable, because "]" is an acceptable continuation only for the first case, but not for the other classes, "]]" - only for the second case, "]]]" - only for the third case, etc.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
This was my solution, however I was told that these classes are not necessary and sufficient. Could please anyone give me a hint how to solve the exercise correctly?
What you wrote down is sufficient to establish that there are infinitely many equivalence classes (and thus prove that the language is not regular).
But it does not give a complete description of all equivalence classes.
For example, consider the string [[][ which has 2 unmatched left parens. It's not in any class that you have listed. Check your description of the classes carefully.
Also, don't forget about the strings in which there are already too many right parens in an early portion. For example, if a string starts with []] then it can't be completed to an element of PAREN no matter what comes after it.