0

Let $\Sigma$ be an alphabet and let $L$ be a language on $\Sigma$. If it is known that all the equivalence classes of $R_L$ are finite, is $L$ regular? If definitely yes, prove. If definitely no, prove. If it cannot be determined give an example to each.

I can immediately say that if $L$ is finite, its equivalence classes of $R_L$ are finite, and it's regular. So I assume that $L$ is infinite. From Nerode theorem I know that $L$ is regular if and only if the number of equivalence classes is finite but it is known that all the equivalence classes are finite, so if it was regular it would have been finite, a contradiction, therefore if $L$ is infinite, and all the equivalence classes of $R_L$ are finite, then $L$ isn't regular.

So I know I need to find an example for both cases. For a regular, any finite language will suffice. But I'm having a problem finding an infinite language with finite equivalence classes

CforLinux
  • 393
  • Equivalence classes under what equivalence relation? – Thomas Andrews Apr 25 '22 at 21:08
  • @ThomasAndrews, $R_L$ from Nerode theorem – CforLinux Apr 25 '22 at 21:10
  • A famous non-regular language on one letter is the language of words of prime length in one letter. Dirichlet’s theorem says that, given any two distinct primes $p,q$ there is a prime $p+qn$ for some integer $n>0,$ so $p+qn$ letters is in the language but $q+qn=q(n+1)$ letters is not. So every equivalence class has $1$ element. You might be able to do this with a simpler set, like $a,a^4,a^9,\dots$ of words with square length. I think all equivalence classes will be finite there, too. – Thomas Andrews Apr 25 '22 at 21:26
  • 1
    Yes, the language of words of square lengths works. If $m^2<n^2$ then $$(m+1)^2=m^2+2m+1<n^2+2m+1<n^2+2n+1=(n+1)^2,$$ so in the language of words of length a square, two words of distinct lengths have a suffix, here a word of length $2m+1,$ which show they are not equivalent. So in a language of one letter, each equivalence class is just one element. – Thomas Andrews Apr 25 '22 at 21:35

0 Answers0