Кодирования

Дана следующая схема кодирования из алфавита $\Sigma =\left\{ a, b, c\right\}$ в алфавит $\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\}$. Найти множества кодов для следующих слов:

Дана следующая схема кодирования из алфавита $\left\{ 0\right\}$ в алфавит $\left\{ a, b\right\} : C=\left\{ (0, a),(00, b)\right\}$. Доказать, что слово $0^{n}$ можно закодировать $F_{n+1}$ способом, где $F_{i}$ — соответствующее число Фибоначчи.

Пусть язык $L$ в алфавите $\left\{ a, b\right\}$, состоит из всех слов, которые начинаются на $a a$ и содержат количество символов $a$ кратное трём. Гомоморфизм $h:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b\right\}^{*}$ задан равенствами $h(0)=a a a$, $h(1)=b a, h(2)=\varepsilon$. Определить, какие из следующих трёх слов принадлежат прообразу $h^{-1}(L)$ языка $L$ при гомоморфизме $h$ :

Пусть язык $L$ в алфавите $\left\{ a, b, c\right\}$ состоит из всех слов, которые начинаются на $a a$ и содержат подслово $b b$. Какая из следующих фраз определяет язык $h(L)$, являющийся образом $L$ при следующем гомоморфизме $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}: h(a)=01, h(b)=11, h(c)=\varepsilon$?

Пусть язык $L$ в алфавите $\left\{ a, b, c\right\}$ состоит из всех слов, которые заканчиваются на $b c c$ и содержат подслово $a c a$. Какая из следующих фраз определяет язык $h(L)$, являющийся образом $L$ при следующем гомоморфизме $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}: h(a)=0, h(b)=10, h(c)=\varepsilon$?

Дана следующая схема кодирования из алфавита $\Sigma =\left\{ 0,1\right\}$ в алфавит $\Omega =\left\{ a, b\right\} : C=\left\{ (00, a a),(01, b),(1, a)\right\}$. Найти результаты кодирования следующих языков, представленных регулярными выражениями:

Дана следующая схема кодирования из алфавита $\Sigma =\left\{ 0,1\right\}$ в алфавит $\Omega =\left\{ a, b\right\} : C=\left\{ (000, a b),(10, a),(11, b b)\right\}$. Найти результаты кодирования следующих языков, представленных регулярными выражениями:

Пусть даны детерминированный конечный автомат $\mathfrak {M}=(\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \left\{ a, b, c\right\} , P, 0, \left\{ 2\right\} )$ с программой $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\}$, а также — гомоморфизм $h:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$, для которого $h(a)=01, h(b)=11$, $h(c)=\varepsilon$. Какие из следующих трёх автоматов $\mathfrak {M}_{1}, \mathfrak {M}_{2}, \mathfrak {M}_{3}$ распознают гомоморфный образ $h\left(L_{A}\right)$?

Дан детерминированный конечный автомат (рис. 33), распознающий некоторый язык $L$. Построить недетерминированный конечный автомат, распознающий язык $C(L)$ для схем кодирования $C$ из задач

Пусть гомоморфизм $C:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b\right\}^{*}$ определяется равенствами $C(0)=a b, C(1)=b, C(2)=a a$.

Построить детерминированный конечный автомат, который распознаёт образ $C(L)$ языка

Пусть гомоморфизм $C:\left\{ 0,1\right\}^{*} \rightarrow \left\{ a, b, c\right\}^{*}$ определяется равенствами $C(0)=a a, C(1)=b c$.

Построить детерминированный конечный автомат, который распознаёт образ $C(L)$ языка

Пусть гомоморфизм $C:\left\{ 0,1,2\right\}^{*} \rightarrow \left\{ a, b, c\right\}^{*}$ определяется равенствами $C(0)=b a, C(1)=\varepsilon , C(2)=b c$.

Построить детерминированный конечный автомат, который распознаёт язык $C(L)$ для языка $L=\left\{ w:\text{ цифры 2 встречаются в }w\text{ блоками чётной длины и хоть один такой блок имеется}\right\}$

Пусть гомоморфизм $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ определяется равенствами $C(a)=10, C(b)=01, C(c)=\varepsilon$.

Построить детерминированный конечный автомат, который распознаёт язык $C^{-1}(L)$ для языка

и содержит чётное количество единиц.

Пусть гомоморфизм $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ определяется равенствами $C(a)=01, C(b)=11, C(c)=\varepsilon$.

Построить детерминированный конечный автомат, который распознаёт прообраз $C^{-1}(L)$ языка

Пусть гомоморфизм $C:\left\{ a, b, c\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ определяется равенствами $C(a)=00, C(b)=011, C(c)=01$.

Построить детерминированный конечный автомат, который распознаёт язык $C^{-1}(L)$ для языка

Доказать, что любую операцию кодирования $C$ для языка можно представить в виде суперпозиции прообраза гомоморфизма $\psi$ и гомоморфизма $\varphi : C(L)=\varphi \left(\psi^{-1}(L)\right)$ для некоторых $\psi$ и $\varphi$.

Определим операцию цилиндрификации, которая обратна операции проекции. Пусть $C$ — проекция алфавита $\Sigma$ на алфавит $\Omega \subseteq \Sigma$. Для любого языка $L \subseteq \Omega^{*}$ определим его цилиндрификацию до алфавита $\Sigma$ как язык

Показать, что для автоматного языка $L$ язык $Z_{\Sigma }(L)$ также является автоматным языком. Предложить процедуру перестройки автомата, распознающего $L$, в автомат, распознающий $Z_{\Sigma }(L)$.

Показать, что если гомоморфизм $C: \Sigma^{*} \rightarrow \Omega^{*}$ является беспрефиксным, то результат обратного кодирования $C^{-1}$ может быть вычислен с помощью конечного преобразователя. Считаем, что $C^{-1}(w)$ может быть любым, если $w \notin \operatorname {rng} C$.

Используя критерий Маркова доказать, что с помощью схем кодирования из задач 484 и 485 каждое слово можно закодировать не более чем одним способом.

С помощью критерия Маркова определить, можно ли для схем кодирования из задач 484 и 485 по коду слова однозначно восстановить само слово.

Построить граф кодирования для первых шести кодовых слов азбуки Морзе: $C_{m}(a)=\lessdot \cdot -» ; C_{m}(b)=\ll -\cdots >; C_{m}(c)=<-\cdot -$ »; $C_{m}(d)=\ll -\cdot >; C_{m}(e)=<\cdot >; C_{m}(f)=<\cdot \cdot -\cdot >$.

С помощью критерия Маркова проверить, будет ли следующий гомоморфизм разнозначным: $C(a)=01, C(b)=100, C(c)=0110$, $C(d)=11, C(e)=0100, C(f)=101$. Если нет, то найти слово, которое нельзя однозначно декодировать.

С помощью критерия Маркова проверить, будет ли следующий гомоморфизм разнозначным: $C(a)=0101, C(b)=100, C(c)=1011$, $C(d)=0010, C(e)=110011, C(f)=00$. Если нет, то найти слово, которое нельзя однозначно декодировать.

Доказать, что беспрефиксные гомоморфизмы разнозначны с помощью критерия Маркова.

Построить с помощью метода Хаффмана оптимальные двоичные кодирования для слов

Построить конечные преобразователи, выполняющие декодирование из задачи 503: построить с помощью метода Хаффмана оптимальные двоичные кодирования для слов

Индукцией по построению доказать, что для двоичного кода Хаффмана сумма в неравенстве Крафта-МакМиллана в точности равна единице.

Доказать, что для любого оптимального двоичного гомоморфизма сумма в неравенстве Крафта-МакМиллана в точности равна единице. Продемонстрировать, что для недвоичных гомоморфизмов это может быть неверно.

Пусть частоты символов $a_{i}, i \in I$, одинаковы. Доказать, что

Требуется построить разнозначный двоичный гомоморфизм из алфавита $\left\{ a, b, c, d, e, f, g, h\right\}$. По некоторым причинам для символов $a, b, c, d, e, f$ решено использовать кодовые слова длин $5,1,3,3,4,8$ соответственно. Известно, что средние частоты символов $g$ и $h$ равны $\frac{1}{8}$ и $\frac{1}{5}$ соответственно. Найти оптимальные длины кодовых слов для $g$ и $h$.

Требуется построить оптимальный двоичный гомоморфизм из алфавита $\left\{ a, b, c, d, e, f, g, h\right\}$. Известно, что первые три символа встречаются одинаково часто, а остальные — намного реже, но тоже с одинаковой частотой.

Пусть $C$ — схема кодирования из алфавита $\Sigma$ в себя, $L$ — автоматный язык алфавита $\Sigma$. Доказать, что язык $C^{*}(L)$ тоже является автоматным:

Таким образом, $C^{*}(L)$ содержит коды слов из $L$, которые можно закодировать, а также все слова из $L$, которые закодировать нельзя.