Formal Languages, Encodings, and Decision Problems: Examples and Counterexamples

Using [L1], we have $L_1{L}_2=\{a\epsilon ,ab\}=\{a,ab\}$. Therefore $(L_1{L}_2)L_3=\{aa,abb,aba,abbb\}\mathrm{.}$

Again by [L1], $L_2{L}_3=\{\epsilon a,\epsilon bb,ba,bbb\}=\{a,bb,ba,bbb\}$. Therefore $L_1(L_2{L}_3)=\{aa,abb,aba,abbb\}\mathrm{.}$

The two explicit calculations in steps 1.1 and 1.2 agree, so this example realizes the identity of [L2] as the four-word set $\{aa,abb,aba,abbb\}$.

The specified decoders recover $n$ from both codewords, so $\sigma$ and $\tau$ are effective encodings. By construction, each bit of $\sigma (n)$ contributes exactly two bits to $\tau (n)$, so $\mathrm{\mid }\tau (n)\mathrm{\mid }=2\mathrm{\mid }\sigma (n)\mathrm{\mid }$ for every $n$. Hence $\mathrm{\mid }\tau (n)\mathrm{\mid }\le 2\mathrm{\mid }\sigma (n)\mathrm{\mid }$ and $\mathrm{\mid }\sigma (n)\mathrm{\mid }\le \mathrm{\mid }\tau (n)\mathrm{\mid }$, which are polynomial bounds in both directions. By [L1], $\sigma$ and $\tau$ are polynomially related.

The displayed example is immediate: $\sigma (13)=1101$ and $\tau (13)=11110011$.

Applying [L2] to the polynomial bound $m(n)=\mathrm{\mid }\tau (n){\mathrm{\mid }}^3$ gives a polynomial bound in $\mathrm{\mid }\sigma (n)\mathrm{\mid }$. Here the calculation is explicit: $\mathrm{\mid }\tau (n){\mathrm{\mid }}^3=(2\mathrm{\mid }\sigma (n)\mathrm{\mid }{)}^3=8\mathrm{\mid }\sigma (n){\mathrm{\mid }}^3$.

The set $L=\{01\}$ is a language over $\mathrm{\Sigma }$: the unique element $01$ is a binary word, so $L\subseteq {\mathrm{\Sigma }}^{\ast }$.

But $01\mathrm{\notin }\mathrm{\Sigma }$, because $\mathrm{\Sigma }$ contains only the two one-letter symbols $0$ and $1$. Therefore $L⊈\mathrm{\Sigma }$.

So $L$ is a counterexample to [A1].

The map $e(w)=1w$ is effective: define a total decoder by removing the first bit from any binary word beginning with $1$, and sending every binary word not beginning with $1$ (including the empty word) to the fixed malformed token. Then the decoder recovers $w$ from $e(w)=1w$.

The codeword $1=e(\epsilon )$ is a proper prefix of $10=e(0)$, so $e$ is not prefix-free.

Therefore $e$ is a counterexample to [A1].