Given a language $L$ over an alphabet $\Sigma$, we say that $u,v \in \Sigma^*$ are prefix equivalent over $L$, denoted $u \sim_L v$, if $uw \in L \iff vw \in L$ holds for all $w \in \Sigma^*$.
Is there a language $L$ over the alphabet $\Sigma = \{ a , b \}$ such that
- $a \sim_L b$, but
- $aa \not\sim_L ba$?
In my opinion, it could be: $L = \{ w \in \Sigma^* | \;\#a\text{ in }w < 2 \;\}$, where "$\#a\text{ in }w$" is the count of signs $a$ in the word $w$.
Thank you
Suppose $a \sim_L b$. Suppose for $w \in \Sigma^\ast$ $a(aw) = (aa)w \in L$, then as $a \sim_L b$, $b(aw) = (ba)w \in L$ as well. And if $a(aw) = (aa)w \notin L$, also $b(aw) = (ba)w \notin L$ for the same reason. So $ba \sim_L aa$.
In essence we can prove: two prefix-equivalent strings remain so if we lengthen them both by the same string.