are two sets of infinity necessarily equal | Automata

Question

we'll define the relation $\equiv_L$ (same one as the one in Myhill-Nerode theorem) as follows:

there exists two string $x,y$ and a language $L$ under the $\Sigma$ alphabet

$x\equiv_Ly$ if there $\nexists$ a suffix $\sigma$ where $x\sigma \in L$ and $y\sigma \notin L$

$x\not\equiv_L y$ if there $\exists$ a suffix $\sigma$ where $x\sigma \in L$ and $y\sigma \notin L$

Rank(L) = number of equivalence classes under the relation $≡_L$

Rank(L) also equal to the number of states in the minimal DFA

let there be $L$ above the binary alphabet and $L^R$ - it's reverse.

is the following statement true or false:

if $L$ is not regular than $Rank(L)=Rank(L^R)$

I answered false because as I understand the rank of a non-regular language may equal to infinity, However, there are different sizes of infinity, known as cardinalities. For example, the cardinality of the set of real numbers is larger than the cardinality of the set of natural numbers. so you can't say that $\infty=\infty$ necessarily.

they claim the statement is true...are they right?

Answer 1

I am afraid that your question is poorly stated and your definition of the Nerode equivalence is wrong. Here are a few advices.

First, try to use some homogeneous notation. If you use $x, y$ for strings, it would be best to use a roman letter, say $s$, for a suffix. Especially, since you denote by $\Sigma$ the alphabet, it is tempting to interpret $\sigma$ as a letter.

Next, you should avoid using existential quantifiers inside an English sentence. I guess you wanted to say

$x \equiv_L y$ if there is no suffix $\sigma$ such that $x\sigma \in L$ and $y\sigma \notin L$

Unfortunately, this definition is wrong. For instance, if $\Sigma = \{0, 1\}$, $L = \{0\}$, $x = 1$ and $y = 0$, there is no $s$ such that $1s \in L$ and $0s \notin L$. However $0 \not\equiv_L 1$.

The right definition should be

$x \equiv_L y$ if, for each $s \in \Sigma^*$, $xs \in L$ if and only if $ys \in L$.

Now, coming back to your question, any language $L$ on a finite alphabet is accepted by the infinite deterministic automaton ${\cal A}_L = (\Sigma^*, \Sigma, \cdot, \varepsilon, L)$ in which $\Sigma^*$ is the set of states, $\Sigma$ is the alphabet, the initial state is the empty string and the set of final states is $L$. The transitions are defined, for each state $u$ and every letter $\sigma$, by $u \cdot \sigma = u \sigma$.

Since $\Sigma$ is finite, $\Sigma^*$ is countable. Thus $L$ is recognized by a countable deterministic automaton. Therefore, its minimal automaton, which is a quotient of ${\cal A}_L$ is also countable. If $L$ is non-regular, its minimal automaton is infinite countable.

As you know, $L$ is regular if and only if $L^R$ is regular. If this is the case, their minimal automaton are both finite (but in general not the same number of states). If they are both non regular, then, as said above, their minimal automaton are both infinite countable.