# How do I show that an equivalence class of a language containing an empty string is infinite

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.

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Mar 31 '16 at 5:43
• @Raphael sorry, I'm not expecting anyone to do my hw. I'm just a tad confused with the wording of the question. {ϵ} would be just a language that has an empty string correct? So you can have a language with an empty string but not necessarily be {ϵ}. I've read up on myhill-nerode and came across the corollary I mentioned but i'm not sure if that's what I should start with to answer the question. – trungnt Mar 31 '16 at 6:27

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.