retagged by
641 views
3 votes
3 votes

Let $L$ be a language over an alphabet $\Sigma$. The equivalence relation $\sim_{\mathrm{L}}$ on the set $\Sigma^{\ast }$ of finite strings over $\Sigma$ is defined by $u \sim_{L} v$ if and only if for all $w \in \Sigma^{\ast }$ it is the case that $u w \in L$ if and only if $v w \in L$.
Suppose that $\mathrm{L}=\mathrm{L}(\mathrm{M})$ is the language accepted by a deterministic finite automaton $\mathrm{M}$. For each $\mathrm{u} \in \Sigma^{\ast }$, let $\mathrm{s}(\mathrm{u})$ be the unique state of $\mathrm{M}$ reached from the initial state after inputting the string $\mathrm{u}$.
Now consider the following statements :

  1. $\mathrm{s}(\mathrm{u})=\mathrm{s}(\mathrm{v})$ implies $\mathrm{u} \sim_{\mathrm{L}} \mathrm{v}$.
  2. $\mathrm{u} \sim_{\mathrm{L}} \mathrm{v}$ implies $\mathrm{s}(\mathrm{u})=\mathrm{s}(\mathrm{v})$.

Which of the above statements is correct?

  1. Only $1$
  2. Only $2$
  3. Both
  4. None
retagged by

1 Answer

6 votes
6 votes

The given equivalence relation is actually the Myhill-Neord relation. Statement $1$ is true because in DFA each string has a unique sequence of states and a unique path.

Since $M$ is some DFA (not necessarily minimal) so statement 2 is false. Consider $\mathrm{L}=\Sigma^{\ast }$, for this $\mathrm{L}$, we will have only one equivalence class in Myhill Neord relation, so all strings in $\Sigma^{\ast }$ will belong to that equivalence class. But assume $M$ is the following DFA of two states which accepts $\Sigma^{\ast }$ then even though empty string and string a are related under $\sim_{\mathrm{L}}$ but still $\mathrm{s}(\epsilon)$ and $\mathrm{s}(\mathrm{a})$ are Not same.



Reference: Myhill Nerode Theorem | Non regular language | Easy Proof of Non regularity of language | GO Classes

https://www.youtube.com/channel/UCyvbBJhLJ-5YqwPA884vj0Q

 

edited by
Answer:

Related questions

2 votes
2 votes
2 answers
2