Codings. Non-Automatic Languages

Given the following coding scheme from the alphabet $\Sigma =\left\{ a, b, c\right\}$ to the alphabet $\Omega =\left\{ 0,1,2\right\} : 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:

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

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 $L=\left\{ w: w\text{ ends in 01 and contains an even number of ones }\right\}$.

Let us define the operation of cylindrification, which is the inverse of 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 a regular language $L$ the language $Z_{\Sigma }(L)$ is also regular. Propose a procedure for rebuilding an automaton recognizing $L$ into an automaton recognizing $Z_{\Sigma }(L)$.

Construct the coding graph for the first six Morse code words.

Using Markov's criterion, determine whether the homomorphism is uniquely decodable: $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.

Prove, using Markov's criterion, that prefix-free homomorphisms are uniquely decodable.

Prove that the homomorphism $\varphi^{\prime }$, constructed in the proof of Lemma 128 on p. 354, is prefix-free.

Lemma 128: Suppose each symbol $a \in \Sigma$ occurs $n_{a}$ times in the word $w \in \Sigma^{*}$, and $a$ and $b$ are the two rarest symbols, with the smallest $n_{a}$ and $n_{b}$. Let $\varphi :\Sigma^{*} \rightarrow \left\{ 0,1\right\}^{*}$ be an optimal binary homomorphism for the word $(w)_{b}^{a}$ (the word $w$ with all occurrences of $a$ replaced by $b$). Then an optimal binary homomorphism for $w$ is given by $\psi_{a}=\varphi_{b} 0, \psi_{b}=\varphi_{b} 1, \psi_{c}=\varphi_{c}$ for $c \notin \left\{ a, b\right\}$.

In the proof (by contradiction), assuming $\psi$ is not optimal produces an optimal homomorphism $\psi^{\prime }$ with $\psi_{a}^{\prime }=u 0, \psi_{b}^{\prime }=u 1$ for some $u \in \left\{ 0,1\right\}^{*}$, from which the homomorphism $\varphi^{\prime }$ for the word $(w)_{b}^{a}$ is constructed by $\varphi_{b}^{\prime }=u, \varphi_{c}^{\prime }=\psi_{c}^{\prime }$ for $c \neq b$.

Using the Huffman method, construct optimal binary encodings for the words

Construct finite transducers that perform the decoding from Problem 269.

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

We need to construct a uniquely decodable binary homomorphism from the alphabet $\left\{ a, b, c, d, e, f, g, h\right\}$. For certain reasons, it has been decided to use code words of lengths $5,1,3,3,4,8$ for the symbols $a, b, c, d, e, f$ 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$.

The reversal of a word $w=a_{1} a_{2} \ldots a_{k}, a_{i} \in \Sigma$ for $i=1, \ldots , k$, is the word $w^{-1}=a_{k} \ldots a_{2} a_{1}$. Show that for a regular language $L$ its reversal — the language $L^{-1}=\left\{ w^{-1}: w \in L\right\}$ — is also regular.

Let $L$ be a regular language over the alphabet $\Sigma$. Prove that the following languages are also regular:

Let $L$ be a regular language over the alphabet $\Sigma =\left\{ a_{1}, \ldots , a_{m}\right\}$, and let $L_{1}, \ldots , L_{m}$ be regular languages over the alphabet $\Delta$. Prove that the language $\operatorname {SUBST}(L)$, obtained from the words of $L$ by replacing each letter $a_{i}$ with some word from $L_{i}$, is also regular. Thus,

Prove that the following languages over the alphabet $\Sigma =\left\{ a, b, c\right\}$ are not regular:

Let $\boldsymbol {V}$ be a finite set of variables, $\boldsymbol {L}=\left\{ \text{ «(», «)», «λ» }\right\}$. Then a $\lambda$-expression is a word over the alphabet $\boldsymbol {V} \cup \boldsymbol {L}$ defined inductively: it is either a variable $x \in \boldsymbol {V}$, or « $\lambda x e_{1}$ », or « $\left(e_{1} e_{2}\right)$ », where $x \in \boldsymbol {V}$, and $e_{1}, e_{2}$ are $\lambda$-expressions. For example, the words « $\lambda x x »$, « $\lambda x(x x) »$, « $\lambda x \lambda x(\lambda x(x x) \lambda x(x x)) »$ are $\lambda$-expressions, while the words « $(x \lambda x) »$, « $\lambda x(\lambda x) »$ and « $\lambda x$ ($(x x) »$ are not $\lambda$-expressions. Prove that the set of $\lambda$-expressions over the alphabet $\boldsymbol {V} \cup \boldsymbol {L}$ is not regular.

Above, in Problem 243 on page 310, an automaton was constructed that checks the correctness of binary addition. Prove that no such automaton exists for the operation of binary multiplication. More precisely, the following language over the alphabet of three-tier symbols is not regular:

x_n y_n z_n : x_i, y_i, z_i 0,1 for i=1, , n and z_n z_1 is the product of the binary numbers x_n x_1 and y_n y_1.

Prove that the following language over the alphabet $\Sigma =\left\{ a, b, c\right\}$ is not regular: