1
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ How is $R_L$ defined? Are you referring to the Myhill-Nerode relation? $\endgroup$
    – dkaeae
    Dec 3, 2018 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, 2018 at 8:45
  • $\begingroup$ I don't understand your second question. "Finite" means "finite cardinality". $\endgroup$
    – David Richerby
    Dec 3, 2018 at 8:50

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.