4 votes 4 votes Let $\text{L}$ be a language over an alphabet $\Sigma$. The equivalence relation $\sim_{\text{L}}$ on the set $\Sigma^{\ast}$ of finite strings over $\Sigma$ is defined by $\mathrm{u} \sim_{\mathrm{L}} \mathrm{v}$ if and only if for all $w \in \Sigma^{\ast}$ it is the case that $u w \in \text{L}$ if and only if $v w \in \text{L}$. Consider the following statements : For a regular language $\text{L}$, the number of $\sim_{\text{L}}$-equivalence classes is finite. For a non-regular language $\text{L}$, the number of $\sim_{\text{L}}$-equivalence classes is infinite. Which of the above statements is/are correct? Only $1$ Only $2$ Both None Theory of Computation goclasses2024-toc-2-weekly-quiz goclasses theory-of-computation regular-language equivalence-class 2-marks + – GO Classes asked Jun 22, 2022 • retagged Jun 17, 2023 by Lakshman Bhaiya GO Classes 399 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes The given equivalence relation is actually Myhill-Neord relation. And we know that a language is regular if and only if the number of equivalence classes in the myhill neord relation are finite. So, both statements are true. GO Classes answered Jun 22, 2022 GO Classes comment Share Follow See all 3 Comments See all 3 3 Comments reply AngshukN commented Nov 4, 2022 reply Follow Share I did not understand how this would apply to non regular languages 0 votes 0 votes Pranavpurkar commented Jan 18, 2023 reply Follow Share @GO Classes , @Deepak Poonia Sir i have one doubt: for myhill nerode equivalence classes to be finite , is it related to finiteness of language? means even if we have infinite language can still there be finite equivalence classes. pls help in this. 0 votes 0 votes Deepak Poonia commented Jan 19, 2023 reply Follow Share For any language $L,$ the number of Myhill-Nerode Equivalence Classes is Finite iff $L$ is Regular. For any language $L,$ the number of Myhill-Nerode Equivalence Classes is Infinite iff $L$ is Non-regular. 2 votes 2 votes Please log in or register to add a comment.
