# If L is regular language then each equivalence class is also regular?

L is a regular language. Let's say that E is one of L's equivalence classes - is it true/false that E is also regular?

The equivalence relation is, from Wikipedia: "Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation RL on strings by the rule that x RL y if there is no distinguishing extension for x and y."

• What is the equivalence relation used to define the equivalence classes? – Steven Apr 23 '20 at 20:25
• From Wikipedia: "Given a language L, and a pair of strings x and y, define a distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation RL on strings by the rule that x RL y if there is no distinguishing extension for x and y." It's all related to Myhill Nerode theorem. – yong Apr 23 '20 at 20:33
• Please edit the question to include all relevant information in the question, so people don't have to read the comments to understand what you are asking. Thank you! – D.W. Apr 23 '20 at 23:30

Given a DFA $$D$$ and a word $$x$$, let $$D(x)$$ denote the state of $$D$$ after reading $$x$$.

Let $$D$$ be a minimal DFA for $$L$$ and $$x,y \in \Sigma^*$$. If $$D(x) \neq D(y)$$ then $$x$$ and $$y$$ have a distinguishing extension. Indeed, if $$x$$ and $$y$$ had no distinguishing extension, it would be possible to construct a DFA $$D'$$ with one less state by merging the states $$D(x)$$ and $$D(y)$$ of $$D$$.

On the converse, if $$D(x)=D(y)$$ then $$x$$ and $$y$$ have no distinguishing extension (since the states reached by $$D$$ from $$D(x)$$ and $$D(y)$$ after reading any string $$z$$ must coincide).

Then, $$x$$ and $$y$$ are in the same equivalence class iff $$D(x)=D(y)=q$$, for some state $$q$$ of $$D$$.

Given a state $$q$$ of $$D$$, the language of all the words $$x \in \Sigma^*$$ such that $$D(x)=q$$ is regular. To see this, consider the DFA obtained from $$D$$ by changing the set of final states to $$\{q\}$$.

• Thanks! But if I'm not wrong, you proved that the language which contains all words in L such that D(x) = q is regular. But an equivalence class doesn't necessarily a subset of L. Why in first place you took x,y in L and not some random words? (which are not necessarily in L) – yong Apr 24 '20 at 9:14
• The same holds if you consider $x,y \in \Sigma^*$. In your question you specified the equivalence relation $\rho$ but you didn't specify the quotient set, so I had assumed the equivalence classes were those in $L / \rho$. I understand now that you are interested in $\Sigma^* / \rho$ instead. – Steven Apr 24 '20 at 10:01
• Yeah, I need to learn how to write math symbols in here so I'd be more precise :) Thanks for the help! – yong Apr 24 '20 at 10:06