0
$\begingroup$

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."

$\endgroup$
3
  • $\begingroup$ What is the equivalence relation used to define the equivalence classes? $\endgroup$
    – Steven
    Apr 23 '20 at 20:25
  • $\begingroup$ 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. $\endgroup$
    – yong
    Apr 23 '20 at 20:33
  • $\begingroup$ 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! $\endgroup$
    – D.W.
    Apr 23 '20 at 23:30
1
$\begingroup$

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\}$.

$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$
    – yong
    Apr 24 '20 at 9:14
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Apr 24 '20 at 10:01
  • $\begingroup$ Yeah, I need to learn how to write math symbols in here so I'd be more precise :) Thanks for the help! $\endgroup$
    – yong
    Apr 24 '20 at 10:06

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.