Let $\Sigma = \{0,1,*\}$ be a finite alphabet and let $\mathcal{L}\subseteq \Sigma^*$ be a formal language defined as follows
- $\{0,1\}\subseteq \mathcal{L}$.
- If $w_1,\dots,w_n\in\mathcal{L}$ then $*w_1w_2\dots w_n*\in\mathcal{L}$
- Nothing more is a an element of $\mathcal{L}$.
I want to prove that
If $*w_1w_2\dots w_n*=*v_1v_2\dots v_m*$ where $w_i, v_j \in \mathcal{L}$ then $n=m$ and $w_i=v_i$ for all $i$.
I was trying to use the fact that every element of $\mathcal{L}$ has an even number of $*$ but maybe I am missing something.
Hint: if you're at all familiar with logic, this proof is (perhaps superficially) very similar to a standard proof of the unique readability theorem in propositional calculus.
So, the first step is going to be to refine our definitions slightly. Your guess about using the even parity of the number of $*$ in each word of $\mathcal{L}$ is correct, and there is a pattern behind it. As a matter of fact, since the stars come in pairs, we can distinguish between left and right stars, so from now on instead of, for example, $*0*$ I am going to write $*_l 0 *_r$ (this is ungainly notation, but is highly illustrative for the proof). So, given a word $w\in \mathcal{L}$ we are going to write $l(w)$ for the number of left stars in $w$, and $r(w)$ for the number of right stars, accordingly. In particular, it should be easy to see that if $w$ is a word, then $r(w)=l(w)$.
Thus begin with a lemma: let $w\in \mathcal{L}$, and let $x$ be a non-empty proper left subword of $w$. Then $l(x)>r(x)$.
Proof: we prove this by induction on the length of $w$. The base case is trivial. So assume the claim holds for all $w$ up to length $n$. Consider a word $w$ with length $n+1$. If $w$ is of the form $*_l\ldots *_l\{0,1\}*_r\ldots *_r$, then we're clearly done as for any proper left subword $x$ we have $l(x)>r(x)$, and hence it's not a word in $\mathcal{L}$. So suppose more generally $w=*_lv_1v_2\ldots v_m*_r$, where $v_i\in \mathcal{L}$, and let $x$ be a proper left subword of $x$. Clearly, depending on how many $v_i$ are included in $x$ (and not forgetting the very first $*_l$!), we have $l(x) = 1 + l(v_1)+l(v_2)+\ldots + l(y_k)$, where $y_k$ is a left subword of $v_k$. By the induction hypothesis we have $$\begin{align} l(x) & \geq 1 + r(v_1) + r(v_2) + \ldots + r(y_k) \\ & > r(v_1) + r(v_2) + \ldots + r(y_k) \\ &= r(x).\end{align}$$ This concludes the proof. I hope you see where this is going. We can now tackle the main question.
Let $w:= *_lw_1w_2\ldots w_n*_r$ and $v:=*_lv_1v_2\ldots v_m*_r$ be equal words in the language $\mathcal{L}$. We will try to derive a contradiction. Suppose there exists $i$ such that $w_i\neq v_i$. Pick the smallest such $i$ (since there
mighthas to be more than one), and assume W.L.O.G. that $w_i$ is a proper left subword of $v_i$ (again, this assumption is tenable because $w$ and $v$ are identical symbol-wise). But since $v_i\in \mathcal{L}$, it follows by the lemma I had just proved that $l(w_i)>r(w_i)$ and hence $w_i\notin \mathcal{L}$. This provides the required contradiction, and so we are done.