HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
showcontaininginfiniteemptylanguagethathowclassstringequivalence

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#55203, answer score: 2

Revisions (0)

No revisions yet.