Can you please help me in understanding how to determine the delay while deciphering codes using appropriate examples ?
I am trying to follow the definition given in the book Codes and Automata by Jean Berstel, Dominique Perrin and Christophe Reutenauer, but I don't seem to follow it.
A subset $X$ of $A^{+}$ is said to have a finite deciphering delay if there exists an integer $d\geq0$ such that the following condition holds : For $x,x'\in X$ ,$y\in X^{d}$, $y'\in X^{*}$, $xy$ is a prefix of $x'y'$ implies $x=x'$.
A few examples that I came across in various books are as follows: The set {${ab,abb,baab}$} has a delay one. The set $ba^*$ has delay one. The set {$aa,ba,b$} is a finite code with infinite delay. The set {$a,a^{k}b$} has delay k.
I am unable to relate the definition to the examples given. It will be of great help if someone can explain this to me.
Thanks.
Hint. Here are some details for two of your examples. You should then be able to uderstand the two other ones.
The set {$aa,ba,b$} is a finite code with infinite deciphering delay. Take $x = b$, $x' = ba$. Now, for all $d \geqslant 0$, $(aa)^d \in X^d$, whence $x(aa)^d, x'(aa)^d \in X^{d+1}$ and $x(aa)^d$ is a prefix of $x'(aa)^d$. However $x \not= x'$ and thus $X$ as infinite deciphering delay.
The set $ba^*$ has delay one. Let $x, x', y, y' \in X$. Then $x= ba^p$, $x' = ba^q$, $y= ba^r$, $y' = ba^s$ for some $p, q, r, s \geqslant 0$. Now if $xy$ is a prefix of $x'y'$, $ba^pba^r$ is a prefix of $ba^qba^s$, which implies that $p = q$. Thus $x = x'$. It follows that the delay of $X$ is $\leqslant 1$. Why is not $0$? Because $X^0 = \{1\}$ ($1$ denotes the empty word) and $b, ba \in XX^0 = X$ but $b$ is a prefix of $ba$.