Give an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct.

Question

Given an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct. We define the matrix as follows. Let $L \subset \Gamma^*$ where $\Gamma$ is alphabet. Then the rows and columns of the boolean matrix $T_L$ are indexed by the words from $\Gamma^*:$ $$T_L = \{T_L(\omega,\tau):\omega,\tau \in \Gamma^*\}$$ where $T_L(\omega,\tau) = 1$ if the concatenation $\omega \tau \in L$, otherwise $0$.

Answer 1

Hint

The question amounts to find an example of a language $L$ of $A^*$ for which the quotients $$ u^{-1}L = \{v \in A^* \mid uv \in L \} $$ are all distinct (for $u \in A^*$). On a one letter alphabet, you can take any nonregular language. On a two-letter alphabet, take $L = \{u\tilde{u} \mid u \in A^* \}$, where, if $u = a_1 \dotsm a_n$, then $\tilde{u} = a_n \dotsm a_1$.