I'm trying to understand why can't we determine the number of equivalence classes of the intersection of L2 which is irregular and L3 which is regular and known to have 3 equivalence classes (L3 can't be empty). Can't we say it has minimum of 1?

Can we determine the number of equivalence classes for an Irregular language L with a star (L*)?


Assuming you are meaning Nerode equivalence classes, the number of classes of a language is finite iff that language is regular.

We cannot make any statement for the intersection of a regular and a non-regular language. That intersection can non-regular, but also regular. Similar for the star of a non-regular language.

Stating that the number of classes is at least one is not very instructive. Isn't that true for all equvalence relations?

  • $\begingroup$ Can you please help me think of a regular language with 3 Nerode equivalence classes that by intersecting with another non-regular language will provide a regular language with a finite number of nerode equivalence classes? Thanks! $\endgroup$
    – Regularity
    Jul 15 '16 at 14:11

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.