If $L\in REG$ then $M$ has a finite number of distinct rows

Question

Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$: $$ m_{x,y}=\begin{cases} 1 & x y\in L\\ 0 & \text{otherwise} \end{cases} $$

I need to show that if $L\in REG$ then there is a finite number of distinct rows in $M$.

$M$ rows resemble me of binary representations of real numbers in $[0,1]$ so perhaps I need to find a function $f:M_i \to [0,1] $ and conclude that since a regular language has a cardinality of $\aleph_0$ there can be only a finite number of distinct rows, but:

• I don't know if that is really the direction to prove this claim.
• I can't find such an $f$. Furthermore, what if $M$'s rows are the unit vectors? There are infinite many distinct rows but the similarity to real numbers binary representation is no longer intuitive to me.

Thanks for your tips!

Answer 1

This is part of the Myhill-Nerode theorem: the rows for $x$ and $y$ are identical if and only if for all $z\in\Sigma^*$, $xz\in L$ iff $yz\in L$ iff there is no distinguishing extension for $x$ and $y$. There is a proof of the theorem at the link, but you might want to try to find one yourself from this HINT: the number of distinct rows is equal to the number of states in the smallest DFA recognizing $L$. (In other words, think in terms of the operation of a DFA recognizing $L$.)

Answer 2

Hint: Let $A$ be a deterministic finite state automaton accepting $L$. For a fixed $x\in \Sigma^*$, the value of $m_{x,y}$ depends only on the state the automaton $A$ is in after reading $x$ (beginning in the initial state).

(Oh dear, I just read Brian's answer and it looks like we have given complementary hints!)