i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.

1)suppose we have some language L over $\Sigma$, can we know if L is regular if all of it equivalence classes of relation $R_L$ is finite?

2)and what about L*? is it finite? i mean the cardinality is infinity(alef), but can it be made into a finite language?

Edit: my question is about Myhill–Nerode relation

i am curious about those and your input would really help me understand more about it

thank you very much!

  • $\begingroup$ How is $R_L$ defined? Are you referring to the Myhill-Nerode relation? $\endgroup$ – dkaeae Dec 3 '18 at 8:39
  • $\begingroup$ yes, thank you very much. i'll state boldly that this is the relation i was refering to $\endgroup$ – mathnoobie Dec 3 '18 at 8:45
  • $\begingroup$ I don't understand your second question. "Finite" means "finite cardinality". $\endgroup$ – David Richerby Dec 3 '18 at 8:50

One of the main results of Myhill–Nerode theory is that a language is regular iff its Myhill–Nerode relation has finitely many equivalence classes. You can find a proof in many online resources. In particular, if all equivalence classes of the Myhill–Nerdoe relation of a language are finite, then it must have infinitely many equivalence classes, and so be non-regular.

The language $L^*$ is finite in two cases: if $L = \emptyset$ or if $L = \{\epsilon\}$. In any other case it is infinite.

| cite | improve this answer | |

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.