Регулярные языки

Ниже приведены диаграммы состояний двух ДКА, $M_{1}$ и $M_{2}$. Ответьте на следующие вопросы для каждой из этих машин.

Приведите формальное описание машин $M_{1}$ и $M_{2}$, изображённых в упражнении 1.1.

Формальное описание ДКА $M$ — это $\left(\left\{ q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\} ,\left\{ \mathrm{u}, \mathrm{d}\right\} , \delta , q_{3},\left\{ q_{3}\right\} \right)$, где $\delta$ задаётся следующей таблицей. Приведите диаграмму состояний этой машины.

Каждый из следующих языков является пересечением двух более простых языков. В каждом пункте постройте ДКА для более простых языков, а затем объедините их с помощью конструкции, обсуждаемой в сноске 3 (стр. 46), чтобы получить диаграмму состояний ДКА для заданного языка. Во всех пунктах $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$.

Каждый из следующих языков является дополнением более простого языка. В каждом пункте постройте ДКА для более простого языка, а затем, используя его, приведите диаграмму состояний ДКА для заданного языка. Во всех пунктах $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$.

Приведите диаграммы состояний ДКА, распознающих следующие языки. Во всех пунктах алфавит равен $\left\{ 0,1\right\}$.

Приведите диаграммы состояний НКА с указанным числом состояний, распознающих каждый из следующих языков. Во всех пунктах алфавит равен $\left\{ 0,1\right\}$.

Используя конструкцию из доказательства теоремы 1.45, приведите диаграммы состояний НКА, распознающих объединение языков, описанных в

Используя конструкцию из доказательства теоремы 1.47, приведите диаграммы состояний НКА, распознающих конкатенацию языков, описанных в

Используя конструкцию из доказательства теоремы 1.49, приведите диаграммы состояний НКА, распознающих звезду языков, описанных в

Докажите, что любой НКА можно преобразовать в эквивалентный ему НКА с единственным допускающим состоянием.

Пусть $D=\left\{ w \mid w\text{ содержит чётное число букв a, нечётное число букв b и не содержит подстроку ab}\right\}$. Приведите ДКА с пятью состояниями, распознающий $D$, и регулярное выражение, порождающее $D$. (Подсказка: опишите $D$ более простым способом.)

Пусть $F$ — язык всех строк над $\left\{ 0,1\right\}$, не содержащих пары единиц, разделённых нечётным числом символов. Приведите диаграмму состояний ДКА с пятью состояниями, распознающего $F$. (Возможно, будет полезно сначала найти НКА с 4 состояниями для дополнения $F$.)

Приведите контрпример, показывающий, что следующая конструкция не доказывает теорему 1.49 о замкнутости класса регулярных языков относительно операции звезды. [^fn1] Пусть $N_{1}=\left(Q_{1}, \Sigma , \delta_{1}, q_{1}, F_{1}\right)$ распознаёт $A_{1}$. Построим $N=\left(Q_{1}, \Sigma , \delta , q_{1}, F\right)$ следующим образом. Предполагается, что $N$ распознаёт $A_{1}^{*}$.

Используя конструкцию из теоремы 1.39, преобразуйте следующие два недетерминированных конечных автомата в эквивалентные им детерминированные конечные автоматы.

Приведите регулярные выражения, порождающие следующие языки (ср. упражнение 1.6). Во всех пунктах алфавит равен $\left\{ 0,1\right\}$.

Используя процедуру, описанную в лемме 1.60, преобразуйте следующие конечные автоматы в регулярные выражения.

В некоторых языках программирования комментарии располагаются между разделителями вида / и /. Пусть $C$ — язык всех корректно оформленных строк-комментариев с такими разделителями. Элемент $C$ должен начинаться с / и заканчиваться на /, но не должен содержать / внутри себя. Для простоты будем считать, что алфавит для $C$ — это $\Sigma =\left\{ \mathrm{a}, \mathrm{b}, /, \# \right\}$.

Пусть $B$ — произвольный язык над алфавитом $\Sigma$. Докажите, что $B=B^{+}$ тогда и только тогда, когда $B B \subseteq B$.

Конечный автомат-преобразователь (finite state transducer, FST) — это разновидность детерминированного конечного автомата, выходом которого является строка, а не просто допуск или отказ. Ниже приведены диаграммы состояний автоматов-преобразователей $T_{1}$ и $T_{2}$.

Каждый переход FST помечен двумя символами: один задаёт входной символ для этого перехода, а другой — выходной символ. Эти два символа записываются через косую черту, /, разделяющую их. В $T_{1}$ переход из $q_{1}$ в $q_{2}$ имеет входной символ 2 и выходной символ 1. У некоторых переходов может быть несколько пар вход-выход, как, например, у перехода из $T_{1}$ из $q_{1}$ в себя. Когда FST работает на входной строке $w$, он считывает входные символы $w_{1} \cdots w_{n}$ один за другим и, начиная с начального состояния, следует по переходам, сопоставляя входные метки с последовательностью символов $w_{1} \cdots w_{n}=w$. Каждый раз, проходя по переходу, автомат выдаёт соответствующий выходной символ. Например, на входе 2212011 машина $T_{1}$ проходит последовательность состояний $q_{1}, q_{2}, q_{2}, q_{2}, q_{2}, q_{1}, q_{1}, q_{1}$ и выдаёт на выходе 1111000. На входе abbb автомат $T_{2}$ выдаёт на выходе 1011. Укажите последовательность состояний и результат работы для каждого из следующих пунктов.

Изучите неформальное определение автомата-преобразователя (FST), данное в упражнении 1.24. Дайте формальное определение этой модели по образцу определения 1.5 (стр. 35). Считайте, что у FST есть входной алфавит $\Sigma$ и выходной алфавит $\Gamma$, но нет множества допускающих состояний. Включите в определение формальное описание вычисления FST. (Подсказка: FST — это пятёрка. Его функция переходов имеет вид $\delta : Q \times \Sigma \longrightarrow Q \times \Gamma$.)

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

Используя решение, полученное в упражнении 1.25, приведите формальное описание машин $T_{1}$ и $T_{2}$, изображённых в упражнении 1.24.

Изучите неформальное определение автомата-преобразователя (FST), данное в упражнении 1.24. Приведите диаграмму состояний FST со следующим поведением. Его входной и выходной алфавиты — $\left\{ 0,1\right\}$. Его выходная строка совпадает с входной строкой на чётных позициях, но инвертирована на нечётных позициях. Например, на входе 0000111 он должен выдавать 1010010.

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

Преобразуйте следующие регулярные выражения в НКА, используя процедуру из теоремы 1.54. Во всех пунктах $\Sigma =\left\{ \mathrm{a}, \mathrm{b}\right\}$.

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

Опишите ошибку в следующем «доказательстве» того, что $0^{*} 1^{*}$ не является регулярным языком. (Ошибка обязательно есть, поскольку $0^{*} 1^{*}$ регулярен.) Доказательство ведётся от противного. Предположим, что $0^{*} 1^{*}$ регулярен. Пусть $p$ — длина накачки для $0^{*} 1^{*}$, задаваемая леммой о накачке. Возьмём в качестве $s$ строку $0^{p} 1^{p}$. Мы знаем, что $s$ принадлежит $0^{*} 1^{*}$, но пример 1.73 показывает, что $s$ нельзя накачать. Таким образом, мы приходим к противоречию. Значит, $0^{*} 1^{*}$ не регулярен.

Для произвольной строки $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$.