• Currently, I do not how easy it is, but, I have a "candidate" language: $L_{k,l} = \{u_1 \# u_2 \# \cdots \# u_k\}$ such that $l < k$, each binary subword ($u_1,\ldots,u_k$) has the same length, and, for each index $i \in \{1,\ldots,|u_1|\}$, there are exactly $l$ subwords whose $i^{th}$ symbols are the same. – Abuzer Yakaryilmaz Jul 14 '13 at 23:39
• $l$ is not part of the input. For each $i \in \{1,\ldots,k\}$, $u_{i} \in \{a,b\}^*$. Moreover, $|u_1| = |u_2| = \cdots = |u_k| > 0$. I thought we could separate $k$ and $k-1$ and no new pass/read would help us. Subwords' lenghts can be arbitrary long and, for each index, there can different $l$ subwords. Do you think $k-1$ head is enough with one-pass? I still could not see it. Maybe, I am missing something obvious(?) – Abuzer Yakaryilmaz Jul 15 '13 at 7:37