is it possible to know if a language is regular if its equivalence classes are finite? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:34:11Z https://cs.stackexchange.com/feeds/question/100935 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/100935 1 is it possible to know if a language is regular if its equivalence classes are finite? mathnoobie https://cs.stackexchange.com/users/97169 2018-12-03T08:33:52Z 2018-12-03T09:00:06Z <p>i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.</p> <p>1)suppose we have some language L over <span class="math-container">$\Sigma$</span>, can we know if L is regular if all of it equivalence classes of relation <span class="math-container">$R_L$</span> is finite?</p> <p>2)and what about L*? is it finite? i mean the cardinality is infinity(alef), but can it be made into a finite language?</p> <p>Edit: my question is about Myhill–Nerode relation</p> <p>i am curious about those and your input would really help me understand more about it</p> <p>thank you very much!</p> https://cs.stackexchange.com/questions/100935/-/100938#100938 0 Answer by Yuval Filmus for is it possible to know if a language is regular if its equivalence classes are finite? Yuval Filmus https://cs.stackexchange.com/users/683 2018-12-03T09:00:06Z 2018-12-03T09:00:06Z <p>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.</p> <p>The language <span class="math-container">$L^*$</span> is finite in two cases: if <span class="math-container">$L = \emptyset$</span> or if <span class="math-container">$L = \{\epsilon\}$</span>. In any other case it is infinite.</p>