Упражнения

ᴬ Ниже приведены диаграммы состояний двух ДКА, $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 о замкнутости класса регулярных языков относительно операции звезды. ¹ Пусть $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^{*}$ не регулярен.