Codings

A coding scheme from the alphabet $\Sigma =\left\{ a, b, c\right\}$ into the alphabet $\Omega =\left\{ 0,1,2\right\}$ is given by: $C=\left\{ (a a, 0),(a b c, 11),(b a, 21),(c, \varepsilon ),(b b, 2), (a b, 22),(b, 1)\right\}$. Find the sets of codes for the following words:

A coding scheme from the alphabet $\left\{ 0\right\}$ into the alphabet $\left\{ a, b\right\}$ is given by: $C=\left\{ (0, a),(00, b)\right\}$. Prove that the word $0^{n}$ can be encoded in $F_{n+1}$ ways, where $F_{i}$ is the corresponding Fibonacci number.

Let the language $L$ over the alphabet $\left\{ a, b\right\}$ consist of all words that begin with $a a$ and contain a number of symbols $a$ that is a multiple of three. The homomorphism $h:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b\right\}^{*}$ is given by the equalities $h(0)=a a a$, $h(1)=b a, h(2)=\varepsilon$. Determine which of the following three words belong to the preimage $h^{-1}(L)$ of the language $L$ under the homomorphism $h$:

Let the language $L$ over the alphabet $\left\{ a, b, c\right\}$ consist of all words that begin with $a a$ and contain the substring $b b$. Which of the following phrases defines the language $h(L)$, the image of $L$ under the following homomorphism $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}: h(a)=01, h(b)=11, h(c)=\varepsilon$?

Let the language $L$ over the alphabet $\left\{ a, b, c\right\}$ consist of all words that end with $b c c$ and contain the substring $a c a$. Which of the following phrases defines the language $h(L)$, the image of $L$ under the following homomorphism $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}: h(a)=0, h(b)=10, h(c)=\varepsilon$?

A coding scheme from the alphabet $\Sigma =\left\{ 0,1\right\}$ into the alphabet $\Omega =\left\{ a, b\right\}$ is given by: $C=\left\{ (00, a a),(01, b),(1, a)\right\}$. Find the results of encoding the following languages, represented by regular expressions:

A coding scheme from the alphabet $\Sigma =\left\{ 0,1\right\}$ into the alphabet $\Omega =\left\{ a, b\right\}$ is given by: $C=\left\{ (000, a b),(10, a),(11, b b)\right\}$. Find the results of encoding the following languages, represented by regular expressions:

Let a deterministic finite automaton $\mathfrak {M}=(\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \left\{ a, b, c\right\} , P, 0, \left\{ 2\right\} )$ be given, with program $P=\left\{ q_{0}, a \rightarrow q_{1} ; q_{0}, b \rightarrow q_{1} ; q_{0}, c \rightarrow q_{0} ; q_{1}, a \rightarrow q_{1} ; q_{1}, b \rightarrow q_{2} ; q_{1}, c \rightarrow q_{2} ; q_{2}, a \rightarrow q_{3} ; q_{2}, b \rightarrow q_{3} ; q_{2}, c \rightarrow q_{2} ; q_{3}, a \rightarrow q_{3} ; q_{3}, b \rightarrow q_{3} ; q_{3}, c \rightarrow q_{3}\right\}$, together with a homomorphism $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$, for which $h(a)=01, h(b)=11$, $h(c)=\varepsilon$. Which of the following three automata $\mathfrak {M}_{1}, \mathfrak {M}_{2}, \mathfrak {M}_{3}$ recognize the homomorphic image $h\left(L_{A}\right)$?

Given a deterministic finite automaton (Fig. 33) recognizing some language $L$. Construct a nondeterministic finite automaton recognizing the language $C(L)$ for the coding schemes $C$ from Problems

Let the homomorphism $C:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b\right\}^{*}$ be defined by the equalities $C(0)=a b, C(1)=b, C(2)=a a$.

Construct a deterministic finite automaton that recognizes the image $C(L)$ of the language

Let the homomorphism $C:\left\{ 0,1\right\}^{*} \rightarrow \left\{ a, b, c\right\}^{*}$ be defined by the equalities $C(0)=a a, C(1)=b c$.

Construct a deterministic finite automaton that recognizes the image $C(L)$ of the language

Let the homomorphism $C:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b, c\right\}^{*}$ be defined by the equalities $C(0)=b a, C(1)=\varepsilon , C(2)=b c$.

Construct a deterministic finite automaton that recognizes the language $C(L)$ for the language $L=\left\{ w:\text{ the digits 2 occur in }w\text{ in blocks of even length, and at least one such block is present}\right\}$

Let the homomorphism $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be defined by the equalities $C(a)=10, C(b)=01, C(c)=\varepsilon$.

Construct a deterministic finite automaton that recognizes the language $C^{-1}(L)$ for the language

and contains an even number of ones.

Let the homomorphism $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be defined by the equalities $C(a)=01, C(b)=11, C(c)=\varepsilon$.

Construct a deterministic finite automaton that recognizes the preimage $C^{-1}(L)$ of the language

Let the homomorphism $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be defined by the equalities $C(a)=00, C(b)=011, C(c)=01$.

Construct a deterministic finite automaton that recognizes the language $C^{-1}(L)$ for the language

Prove that any encoding operation $C$ for a language can be represented as a superposition of the preimage of a homomorphism $\psi$ and a homomorphism $\varphi : C(L)=\varphi \left(\psi^{-1}(L)\right)$ for some $\psi$ and $\varphi$.

Let us define the cylindrification operation, which is inverse to the projection operation. Let $C$ be the projection of the alphabet $\Sigma$ onto the alphabet $\Omega \subseteq \Sigma$. For any language $L \subseteq \Omega^{*}$ define its cylindrification to the alphabet $\Sigma$ as the language

Show that for an automatic language $L$ the language $Z_{\Sigma }(L)$ is also an automatic language. Propose a procedure for rebuilding an automaton recognizing $L$ into an automaton recognizing $Z_{\Sigma }(L)$.

Show that if the homomorphism $C: \Sigma^{*} \rightarrow \Omega^{*}$ is prefix-free, then the result of the inverse encoding $C^{-1}$ can be computed by a finite transducer. We assume $C^{-1}(w)$ may be anything if $w \notin \operatorname {rng} C$.

Using the Markov criterion, prove that with the aid of the coding schemes from Problems 484 and 485, every word can be encoded in at most one way.

Using the Markov criterion, determine whether, for the coding schemes from Problems 484 and 485, the original word can be uniquely recovered from the code of a word.

Construct the coding graph for the first six code words of Morse code: $C_{m}(a)=\text{``}\cdot -\text{''}; C_{m}(b)=\text{``}-\cdots \text{''}; C_{m}(c)=\text{``}-\cdot -\cdot \text{''}$; $C_{m}(d)=\text{``}-\cdot \cdot \text{''}; C_{m}(e)=\text{``}\cdot \text{''}; C_{m}(f)=\text{``}\cdot \cdot -\cdot \text{''}$.

Using the Markov criterion, check whether the following homomorphism is unambiguous: $C(a)=01, C(b)=100, C(c)=0110$, $C(d)=11, C(e)=0100, C(f)=101$. If not, find a word that cannot be uniquely decoded.

Using the Markov criterion, check whether the following homomorphism is unambiguous: $C(a)=0101, C(b)=100, C(c)=1011$, $C(d)=0010, C(e)=110011, C(f)=00$. If not, find a word that cannot be uniquely decoded.

Prove that prefix-free homomorphisms are unambiguous, using the Markov criterion.

Using the Huffman method, construct optimal binary encodings for the (Russian) words

Construct finite transducers performing the decoding from Problem 503: using the Huffman method, construct optimal binary encodings for the words

By induction on the construction, prove that for a binary Huffman code, the sum in the Kraft-McMillan inequality is exactly equal to one.

Prove that for any optimal binary homomorphism, the sum in the Kraft-McMillan inequality is exactly equal to one. Demonstrate that for non-binary homomorphisms this may fail.

Let the frequencies of the symbols $a_{i}, i \in I$, be equal. Prove that

We need to construct an unambiguous binary homomorphism from the alphabet $\left\{ a, b, c, d, e, f, g, h\right\}$. For certain reasons, for the symbols $a, b, c, d, e, f$ it has been decided to use code words of lengths $5,1,3,3,4,8$ respectively. It is known that the average frequencies of the symbols $g$ and $h$ are $\frac{1}{8}$ and $\frac{1}{5}$ respectively. Find the optimal lengths of the code words for $g$ and $h$.

We need to construct an optimal binary homomorphism from the alphabet $\left\{ a, b, c, d, e, f, g, h\right\}$. It is known that the first three symbols occur equally often, while the rest occur much more rarely, but also with equal frequency.

Let $C$ be a coding scheme from the alphabet $\Sigma$ into itself, and let $L$ be an automatic language over the alphabet $\Sigma$. Prove that the language $C^{*}(L)$ is also automatic:

Thus $C^{*}(L)$ contains the codes of words from $L$ that can be encoded, together with all words from $L$ that cannot be encoded.