1

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?

user4530988
  • 13

1 Answers1

0

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.

Ted
  • 33,788
  • Thanks a lot for your hints! Will it be correct to write: The equivalence classes are:
    1. x, y are such strings that at the beginning have a substring "a]" (a ∈ PAREN), and z is any string from Σ, which means both x and y behave equivalently under extension z, meaning - x⋅z and y⋅z are not from PAREN;
    2. x, y are such strings that have k-number of unmatched left "[", z is a string of the type "]]]]...]]]" with k-number of right "]";
    3. x, y have (k+1) unmatched left "[", z is a string of the type "]]]]...]]]" with (k+1) of right "]";

    ... And they are all distinguishable.

     – user4530988 Oct 31 '16 at 17:46
  • I think you have the right idea, but what's k? – Ted Nov 01 '16 at 05:45
  • natural number. or it's better to paraphrase the 2 and 3 to: 2) x and y - strings with one [, then z is ]. 3) x and y - strings that have two unmatched left parentheses in any place, and z is ]] ... infinitely – user4530988 Nov 01 '16 at 06:59
  • okay. Don't forget one last case, which are the elements of PAREN itself. They belong to a single class. – Ted Nov 01 '16 at 15:51