Задачи

Для произвольной строки $w=w_{1} w_{2} \cdots w_{n}$ обращением $w$, обозначаемым $w^{\mathcal{R}}$, называется строка $w$, записанная в обратном порядке, $w_{n} \cdots w_{2} w_{1}$. Для произвольного языка $A$ положим $A^{\mathcal{R}}=\left\{ w^{\mathcal{R}} \mid w \in A\right\}$. Покажите, что если $A$ регулярен, то и $A^{\mathcal{R}}$ регулярен.

Пусть

$\Sigma_{3}$ содержит все столбцы высотой 3, состоящие из нулей и единиц. Строка символов из $\Sigma_{3}$ задаёт три строки нулей и единиц. Будем считать каждую строку двоичным числом и положим

Например,

Покажите, что $B$ регулярен. (Подсказка: работать с $B^{\mathcal{R}}$ проще. Вы можете использовать результат, утверждаемый в задаче 1.31.)

Пусть

Здесь $\Sigma_{2}$ содержит все столбцы высотой два, состоящие из нулей и единиц. Строка символов из $\Sigma_{2}$ задаёт две строки нулей и единиц. Будем считать каждую строку двоичным числом и положим

Например, $\left[\begin{array}{l}0 \\ 0\end{array}\right]\left[\begin{array}{l}0 \\ 1\end{array}\right]\left[\begin{array}{l}1 \\ 1\end{array}\right]\left[\begin{array}{l}0 \\ 0\end{array}\right] \in C$, а $\left[\begin{array}{l}0 \\ 1\end{array}\right]\left[\begin{array}{l}0 \\ 1\end{array}\right]\left[\begin{array}{l}1 \\ 0\end{array}\right] \notin C$. Покажите, что $C$ регулярен. (Вы можете использовать результат, утверждаемый в задаче 1.31.)

Пусть $\Sigma_{2}$ — то же, что и в задаче 1.33. Будем считать каждую строку двоичным числом и положим

Например, $\left[\begin{array}{l}0 \\ 0\end{array}\right]\left[\begin{array}{l}1 \\ 0\end{array}\right]\left[\begin{array}{l}1 \\ 1\end{array}\right]\left[\begin{array}{l}0 \\ 0\end{array}\right] \in D$, а $\left[\begin{array}{l}0 \\ 0\end{array}\right]\left[\begin{array}{l}0 \\ 1\end{array}\right]\left[\begin{array}{l}1 \\ 1\end{array}\right]\left[\begin{array}{l}0 \\ 0\end{array}\right] \notin D$. Покажите, что $D$ регулярен.

Пусть $\Sigma_{2}$ — то же, что и в задаче 1.33. Будем считать верхнюю и нижнюю строки строками из нулей и единиц, и положим

Задача 1.33: $\Sigma_{2}$ содержит все столбцы из нулей и единиц высоты два,

Строка символов из $\Sigma_{2}$ задаёт две строки из нулей и единиц. Покажите, что $E$ не является регулярным.

Пусть $B_{n}=\left\{ \mathrm{a}^{k} \mid k \text{ кратно } n\right\}$. Покажите, что для каждого $n \geq 1$ язык $B_{n}$ регулярен.

Пусть $C_{n}=\left\{ x \mid x\text{ — двоичное число, кратное }n\right\}$. Покажите, что для каждого $n \geq 1$ язык $C_{n}$ регулярен.

all-NFA $M$ — это пятёрка $\left(Q, \Sigma , \delta , q_{0}, F\right)$, которая допускает $x \in \Sigma^{*}$, если каждое возможное состояние, в котором может оказаться $M$ после чтения входной строки $x$, является состоянием из $F$. Заметим, что, в отличие от него, обычный НКА допускает строку, если хотя бы одно из этих возможных состояний является допускающим. Докажите, что all-NFA распознают класс регулярных языков.

Конструкция из теоремы 1.54 показывает, что каждый ОНКА (обобщённый НКА, GNFA) эквивалентен ОНКА всего с двумя состояниями. Мы можем показать, что для ДКА имеет место противоположное явление. Докажите, что для каждого $k>1$ существует язык $A_{k} \subseteq \left\{ 0,1\right\}^{*}$, который распознаётся ДКА с $k$ состояниями, но не распознаётся ни одним ДКА с $k-1$ состояниями.

Напомним, что строка $x$ является префиксом строки $y$, если существует строка $z$ такая, что $x z=y$, и что $x$ является собственным префиксом $y$, если, кроме того, $x \neq y$. В каждом из следующих пунктов определяется операция над языком $A$. Покажите, что класс регулярных языков замкнут относительно этой операции.

Для языков $A$ и $B$ назовём идеальным перемешиванием (perfect shuffle) $A$ и $B$ язык

Покажите, что класс регулярных языков замкнут относительно операции идеального перемешивания.

Для языков $A$ и $B$ назовём перемешиванием (shuffle) $A$ и $B$ язык

Покажите, что класс регулярных языков замкнут относительно операции перемешивания.

Пусть $A$ — произвольный язык. Определим $\operatorname {DROP-OUT}(A)$ как язык, содержащий все строки, которые можно получить, удалив один символ из некоторой строки языка $A$. Таким образом, $\operatorname {DROP-OUT}(A)=\left\{ x z \mid x y z \in A \text{ где } x, z \in \Sigma^{*}, y \in \Sigma \right\}$. Покажите, что класс регулярных языков замкнут относительно операции DROP-OUT. Приведите как доказательство «на картинке», так и более формальное доказательство с помощью построения, как в теореме 1.47.

Пусть $B$ и $C$ — языки над алфавитом $\Sigma =\left\{ 0,1\right\}$. Определим $B \stackrel{1}{\leftarrow } C=\left\{ w \in B \mid \text{ для некоторого }y \in C\text{ строки }w\text{ и }y\text{ содержат поровну единиц}\right\}$. Покажите, что класс регулярных языков замкнут относительно операции $\stackrel{1}{\leftarrow }$.

• Пусть $A / B=\left\{ w \mid w x \in A\text{ для некоторого }x \in B\right\}$. Покажите, что если $A$ регулярен, а $B$ — произвольный язык, то $A / B$ регулярен.

Докажите, что следующие языки не являются регулярными. Вы можете использовать лемму о накачке и замкнутость класса регулярных языков относительно объединения, пересечения и дополнения.

Пусть $\Sigma =\left\{ 1, \# \right\}$ и $Y=\left\{ w \mid w=x_{1} \# x_{2} \# \cdots \# x_{k} \text{ при } k \geq 0, \text{ каждое } x_{i} \in 1^{*}, \text{ и } x_{i} \neq x_{j} \text{ при } i \neq j\right\}$. Докажите, что $Y$ не является регулярным.

Пусть $\Sigma =\left\{ 0,1\right\}$ и $D=\left\{ w \mid w\text{ содержит поровну вхождений подстрок 01 и 10}\right\}$. Так, $101 \in D$, поскольку 101 содержит одно вхождение 01 и одно вхождение 10, а $1010 \notin D$, поскольку 1010 содержит два вхождения 10 и одно вхождение 01. Покажите, что $D$ — регулярный язык.

Изучите неформальное определение автомата-преобразователя (FST), данное в упражнении 1.24. Докажите, что ни один FST не может выдавать $w^{\mathcal{R}}$ для каждой входной строки $w$, если входной и выходной алфавиты равны $\left\{ 0,1\right\}$.

Упражнение 1.24: Автомат-преобразователь с конечным числом состояний (FST) — это тип детерминированного конечного автомата, выход которого является строкой, а не просто допуском или отклонением. Каждый переход FST помечен двумя символами: один обозначает входной символ для этого перехода, а другой — выходной символ, причём эти два символа записываются через слэш, /, разделяющий их. Некоторые переходы могут иметь несколько пар вход-выход. Когда FST вычисляет на входной строке $w$, он берёт входные символы $w_{1} \cdots w_{n}$ по одному и, начиная с начального состояния, следует переходам, сопоставляя входные метки с последовательностью символов $w_{1} \cdots w_{n}=w$. Каждый раз, проходя по переходу, он выводит соответствующий выходной символ.

Пусть $x$ и $y$ — строки, а $L$ — произвольный язык. Будем говорить, что $x$ и $y$ различимы языком $\boldsymbol {L}$, если существует строка $z$, такая что ровно одна из строк $x z$ и $y z$ принадлежит $L$; в противном случае, то есть если для каждой строки $z$ выполнено $x z \in L$, как только $y z \in L$, будем говорить, что $x$ и $y$ неразличимы языком $\boldsymbol {L}$. Если $x$ и $y$ неразличимы языком $L$, будем писать $x \equiv_{L} y$. Покажите, что $\equiv_{L}$ является отношением эквивалентности.

Теорема Майхилла-Нероуда. Обратитесь к задаче 1.51. Пусть $L$ — язык, а $X$ — множество строк. Будем говорить, что $X$ попарно различимо языком $\boldsymbol {L}$, если каждые две различные строки из $X$ различимы языком $L$. Назовём индексом языка $\boldsymbol {L}$ максимальное число элементов в множестве, попарно различимом языком $L$. Индекс языка $L$ может быть конечным или бесконечным.

Пусть $\Sigma =\left\{ 0,1,+,=\right\}$ и

Покажите, что $A D D$ не является регулярным.

Рассмотрим язык $F=\left\{ \mathrm{a}^{i} \mathrm{~ b}^{j} \mathrm{c}^{k} \mid i, j, k \geq 0, \text{ и если } i=1, \text{ то } j=k\right\}$.

Лемма о накачке утверждает, что у каждого регулярного языка есть длина накачки $p$, такая что любую строку языка длины не менее $p$ можно накачать. Если $p$ — длина накачки для языка $A$, то и любая длина $p^{\prime } \geq p$ также является длиной накачки. Минимальной длиной накачки для $A$ называется наименьшее $p$, являющееся длиной накачки для $A$. Например, если $A=01^{*}$, минимальная длина накачки равна 2. Причина в том, что строка $s=0$ принадлежит $A$ и имеет длину 1, но её нельзя накачать; однако любая строка из $A$ длины 2 или более содержит 1 и потому может быть накачана, если разбить её так, что $x=0, y=1$, а $z$ — остаток. Для каждого из следующих языков укажите минимальную длину накачки и обоснуйте свой ответ.

• Если $A$ — множество натуральных чисел, а $k$ — натуральное число, большее 1, положим

Здесь мы не допускаем ведущих нулей в представлении числа. Например, $B_{2}(\left\{ 3,5\right\} )=\left\{ 11,101\right\}$ и $B_{3}(\left\{ 3,5\right\} )=\left\{ 10,12\right\}$. Приведите пример множества $A$, для которого $B_{2}(A)$ регулярен, а $B_{3}(A)$ не регулярен. Докажите, что ваш пример работает.

• Если $A$ — произвольный язык, пусть $A_{\frac{1}{2}-}$ — множество всех первых половин строк из $A$, то есть

Покажите, что если $A$ регулярен, то и $A_{\frac{1}{2}-}$ регулярен.

• Если $A$ — произвольный язык, пусть $A_{\frac{1}{3}-\frac{1}{3}}$ — множество всех строк из $A$ с удалённой средней третью, то есть

Покажите, что если $A$ регулярен, то $A_{\frac{1}{3}-\frac{1}{3}}$ не обязательно регулярен.

• Пусть $M=\left(Q, \Sigma , \delta , q_{0}, F\right)$ — ДКА, а $h$ — некоторое состояние $M$, называемое его «домом». Синхронизирующей последовательностью для $M$ и $h$ называется строка $s \in \Sigma^{*}$, для которой $\delta (q, s)=h$ при каждом $q \in Q$. (Здесь мы расширили $\delta$ на строки, так что $\delta (q, s)$ равно состоянию, в котором окажется $M$, если начать в состоянии $q$ и прочитать вход $s$.) Будем говорить, что $M$ синхронизируем, если для него существует синхронизирующая последовательность для некоторого состояния $h$. Докажите, что если $M$ — синхронизируемый ДКА с $k$ состояниями, то у него есть синхронизирующая последовательность длины не более $k^{3}$. Можете ли вы улучшить эту оценку?

Пусть $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$. Для каждого $k \geq 1$ пусть $C_{k}$ — язык, состоящий из всех строк, содержащих a ровно на $k$-м месте от правого конца. Таким образом, $C_{k}=\Sigma^{*} \mathrm{a} \Sigma^{k-1}$. Опишите НКА с $k+1$ состояниями, распознающий $C_{k}$, как в виде диаграммы состояний, так и в виде формального описания.

Рассмотрим языки $C_{k}$, определённые в задаче 1.60. Докажите, что при каждом $k$ ни один ДКА не может распознавать $C_{k}$, имея менее $2^{k}$ состояний.

Задача 1.60: Пусть $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$. Для каждого $k \geq 1$ пусть $C_{k}$ — язык, состоящий из всех строк, содержащих символ a ровно на $k$-м месте от правого конца. Таким образом, $C_{k}=\Sigma^{*} \mathrm{a} \Sigma^{k-1}$.

Пусть $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$. Для каждого $k \geq 1$ пусть $D_{k}$ — язык, состоящий из всех строк, содержащих хотя бы одну a среди последних $k$ символов. Таким образом, $D_{k}=\Sigma^{*} \mathrm{a}(\Sigma \cup \varepsilon )^{k-1}$. Опишите ДКА не более чем с $k+1$ состояниями, распознающий $D_{k}$, как в виде диаграммы состояний, так и в виде формального описания.

Пусть $N$ — НКА с $k$ состояниями, распознающий некоторый язык $A$.

• Докажите, что для каждого $n>0$ существует язык $B_{n}$, для которого

Гомоморфизмом называется функция $f: \Sigma \longrightarrow \Gamma^{*}$, отображающая один алфавит в строки над другим алфавитом. Мы можем распространить $f$ на строки, определив $f(w)=f\left(w_{1}\right) f\left(w_{2}\right) \cdots f\left(w_{n}\right)$, где $w=w_{1} w_{2} \cdots w_{n}$ и каждое $w_{i} \in \Sigma$. Далее мы распространим $f$ на языки, определив $f(A)=\left\{ f(w) \mid w \in A\right\}$ для произвольного языка $A$.

• Назовём вращательным замыканием языка $A$ множество $R C(A)=\left\{ y x \mid x y \in A\right\}$.

• В традиционном способе снятия колоды игральных карт колода произвольно делится на две части, которые меняются местами перед тем, как колода складывается заново. В более сложном варианте снятия, называемом снятием Скарна, колода делится на три части, и при сборке средняя часть кладётся первой. Возьмём снятие Скарна за основу для операции над языками. Для языка $A$ положим $C U T(A)=\left\{ y x z \mid x y z \in A\right\}$.

Пусть $\Sigma =\left\{ 0,1\right\}$. Пусть $W W_{k}=\left\{ w w \mid w \in \Sigma^{*}, \text{ и } w \text{ имеет длину } k\right\}$.

Определим операцию avoids («избегает») для языков $A$ и $B$ как $A$ avoids $B=\left\{ w \mid w \in A\text{, и }w\text{ не содержит в качестве подстроки ни одной строки из }B\right\}$. Докажите, что класс регулярных языков замкнут относительно операции avoids.

Пусть $\Sigma =\left\{ 0,1\right\}$.

Пусть $M_{1}$ и $M_{2}$ — ДКА, имеющие $k_{1}$ и $k_{2}$ состояний соответственно, и пусть $U=L\left(M_{1}\right) \cup L\left(M_{2}\right)$.

Пусть $\Sigma =\left\{ 0,1, \# \right\}$. Пусть $C=\left\{ x \# x^{\mathcal{R}} \# x \mid x \in \left\{ 0,1\right\}^{*}\right\}$. Покажите, что $\bar{C}$ является КС-языком.