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$.
Give an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct.
Asked
Active
Viewed 55 times
1 Answers
0
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$.
J.-E. Pin
- 40,163
-
Can you explain in more detail?? What do you mean by quotients of a language?? – eChung00 Oct 29 '13 at 20:32
-
I gave you the definition. The (left) quotient of a language $L$ by a word $u$ is the language $u^{-1}L$. – J.-E. Pin Oct 30 '13 at 09:09