Cheap and Secure Web Hosting Provider : See Now

# Why the number of equivalence classes for the intersection of an irregular language L2 and a regular languge L3 (with 3 EC) can't be determined?

, ,
Problem Detail:

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*)?

###### Answered By : Hendrik Jan

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?

Question Source : http://cs.stackexchange.com/questions/60442

3200 people like this