Кодирования. Неавтоматные языки

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

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

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

Построить детерминированный конечный автомат, который распознаёт язык $C^{-1}(L)$ для языка $L=\left\{ w: w\text{ заканчивается на 01 и содержит чётное количество единиц }\right\}$.

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

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

Построить граф кодирования для первых шести кодовых слов азбуки Морзе.

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

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

Доказать, что гомоморфизм $\varphi^{\prime }$, построенный в доказательстве леммы 128 на стр. 354, является беспрефиксным.

Лемма 128: Пусть каждый символ $a \in \Sigma$ встречается $n_{a}$ раз в слове $w \in \Sigma^{*}$, а $a$ и $b$ — два самых редких символа, с наименьшими $n_{a}$ и $n_{b}$. Пусть $\varphi :\Sigma^{*} \rightarrow \left\{ 0,1\right\}^{*}$ — оптимальный двоичный гомоморфизм для слова $(w)_{b}^{a}$ (слова $w$, в котором все вхождения $a$ заменены на $b$). Тогда оптимальным для слова $w$ двоичным гомоморфизмом будет такой: $\psi_{a}=\varphi_{b} 0, \psi_{b}=\varphi_{b} 1, \psi_{c}=\varphi_{c}$, если $c \notin \left\{ a, b\right\}$.

В доказательстве (от противного) из предположения, что $\psi$ не оптимален, строится оптимальный гомоморфизм $\psi^{\prime }$ такой, что $\psi_{a}^{\prime }=u 0, \psi_{b}^{\prime }=u 1$ для некоторого $u \in \left\{ 0,1\right\}^{*}$, из которого для слова $(w)_{b}^{a}$ строится гомоморфизм $\varphi^{\prime }$: $\varphi_{b}^{\prime }=u, \varphi_{c}^{\prime }=\psi_{c}^{\prime }$ при $c \neq b$.

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

Построить конечные преобразователи, выполняющие декодирование из задачи 269.

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

Требуется построить разнозначный двоичный гомоморфизм из алфавита $\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$.

Обращением слова $w=a_{1} a_{2} \ldots a_{k}, a_{i} \in \Sigma$ при $i=1, \ldots , k$, называется слово $w^{-1}=a_{k} \ldots a_{2} a_{1}$. Показать, что для автоматного языка $L$ его обращение — язык $L^{-1}=\left\{ w^{-1}: w \in L\right\}$ — также является автоматным.

Пусть $L$ — автоматный язык в алфавите $\Sigma$. Доказать, что автоматными являются и следующие языки:

Пусть $L$ — автоматный язык в алфавите $\Sigma =\left\{ a_{1}, \ldots , a_{m}\right\}$, а $L_{1}, \ldots , L_{m}$ — это автоматные языки в алфавите $\Delta$. Доказать, что автоматным является и язык $\operatorname {SUBST}(L)$, полученный из слов $L$ заменой каждой буквы $a_{i}$ на некоторое слово из $L_{i}$. Таким образом,

Доказать, что следующие языки в алфавите $\Sigma =\left\{ a, b, c\right\}$ не являются автоматными:

Пусть $\boldsymbol {V}$ — это конечное множество переменных, $\boldsymbol {L}=\left\{ \text{ «(», «)», «λ» }\right\}$. Тогда $\lambda$-выражение — это слово в алфавите $\boldsymbol {V} \cup \boldsymbol {L}$, определяемое индуктивно: либо переменная $x \in \boldsymbol {V}$, либо « $\lambda x e_{1}$ », либо « $\left(e_{1} e_{2}\right)$ », где $x \in \boldsymbol {V}$, $e_{1}, e_{2}$ — $\lambda$-выражения. Например, слова « $\lambda x x »$, « $\lambda x(x x) »$, « $\lambda x \lambda x(\lambda x(x x) \lambda x(x x)) »$ — это $\lambda$-выражения, а слова « $(x \lambda x) »$, « $\lambda x(\lambda x) »$ и « $\lambda x$ ($(x x) » \lambda$-выражениями не являются. Доказать, что множество $\lambda$-выражений в алфавите $\boldsymbol {V} \cup \boldsymbol {L}$ не является автоматным.

Выше в задаче 243 на стр. 310 строился автомат, который проверял правильность сложения двоичных чисел. Доказать, что для операции умножения двоичных чисел такого автомата не существует. Точнее, следующий язык в алфавите трёхэтажных символов не является автоматным:

x_n y_n z_n : x_i, y_i, z_i 0,1 для i=1, , n и z_n z_1 — это произведение двоичных чисел x_n x_1 и y_n y_1.

Доказать, что следующий язык в алфавите $\Sigma =\left\{ a, b, c\right\}$ не является автоматным: