4
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Mar 31, 2016 at 5:43
  • $\begingroup$ @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. $\endgroup$
    – trungnt
    Mar 31, 2016 at 6:27

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.