Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The question is as follows:
Let $L$ be a language (not necessarily regular) over an alphabet. Show that if the equivalence class containing the empty string $[ \epsilon ]$ is not $\{ \epsilon \}$, then it is infinite.
How do I go about answering this? Would I need to use Myhill-Nerode theorem? From what I've read there's a corollary from the theorem that if a language defines an infinite set of equivalence classes, it is not regular. I'm not sure if that helps answer my question though.
Let $A$ be the alphabet. I suppose that the equivalence you are referring to is the equivalence $\sim$ defined on $A^*$ by $u \sim v$ if and only if, for all $x \in A^*$, $$ ux \in L \Leftrightarrow vx \in L $$ Now suppose there is a word $u \in A^+$ such that $u \sim \varepsilon$. Then by definition, $x \in L$ if and only if $ux \in L$. It follows by induction on $n$, that for all $n > 0$, $x \in L$ if and only if $u^nx \in L$ and thus $[\varepsilon]$ contains $u^*$. If the alphabet is nonempty, it follows that $[\varepsilon]$ is infinite.
