W4. Полные и неполные FSA, операции над FSA (дополнение, пересечение, объединение, разность), FST, регулярные языки, свойства замкнутости

1. Краткое содержание

1.1 Представления конечных автоматов

На предыдущих лекциях мы изучили формальное определение конечного автомата (FSA). Теперь рассмотрим два важных варианта задания функции переходов: полные и неполные FSA.

1.1.1 Полные FSA

Полный FSA — это автомат, у которого функция переходов всюду определена (total): она задана для каждой пары «состояние — входной символ». Формально, для полного FSA функция должна удовлетворять:

определена

То есть в каком бы состоянии ни находился автомат и какой бы символ он ни прочитал, всегда есть определённый переход в некоторое состояние (в том числе в то же самое через петлю).

Зачем нужна полнота? Полный FSA гарантирует, что любую строку над алфавитом можно обработать, не «застревая». У автомата всегда есть однозначное конечное состояние — принимающее или отвергающее.

Пример: FSA над алфавитом с двумя состояниями (принимающее) и (непринимающее):

• Из : на входе 0 → остаёмся в , на входе 1 → переход в
• Из : на входе 0 → переход в , на входе 1 → остаёмся в

Это полный автомат: для каждой пары переход задан.

1.1.2 Неполные FSA

Неполный FSA (также частичный FSA) — автомат, у которого функция частична: для некоторых пар «состояние — символ» переход не задан. Формально:

неопределена

Что происходит при неопределённом переходе? Если при разборе строки FSA попадает в ситуацию, где не определена, строка автоматически отвергается — автомат не может продолжить работу и достичь принимающего состояния.

Пример: FSA над алфавитом :

• (старт) → на a переход в ; на b переход не определён
• (принимающее) → на b остаёмся в ; на a не определено

Этот FSA принимает строки вида «a», за которым следует ноль или больше символов b (). Строка, начинающаяся с b, или содержащая a после первой позиции, приводит к неопределённому переходу и отвергается.

Графическое представление: на диаграммах неполные FSA просто не рисуют стрелок для неопределённых переходов. У полных FSA показаны все переходы.

1.1.3 Превращение неполного FSA в полный

Любой неполный FSA можно преобразовать в эквивалентный полный, добавив состояние-ловушку (ошибочное состояние, сток). Процедура:

1. Добавить новое непринимающее состояние (или — от «error»)
2. Для каждого неопределённого задать переход в ловушку:
3. Петли в ловушке по всем символам: для всех

Свойство ловушки: войдя в неё, автомат уже не выйдет. Так как она непринимающая, любая строка, приводящая в неё, отвергается.

Пример: дополнение неполного FSA выше:

• Добавить (непринимающее)
• на b →
• на a →
• на a →
• на b →

Теперь для каждой пары «состояние — символ» переход определён: FSA полон, а распознаваемый язык тот же.

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

Регулярный язык — любой язык, который может быть распознан (принят) конечным автоматом. Это базовое понятие теоретической информатики.

Формальное определение: язык называется регулярным тогда и только тогда, когда существует конечный автомат такой, что , где:

То есть состоит ровно из тех строк, которые при обработке приводят в принимающее состояние.

Важные свойства регулярных языков:

1. Разрешимость: для любого регулярного и любой строки алгоритмически можно проверить, принадлежит ли , моделируя FSA
2. Конечность описания: регулярные языки задаются FSA с конечным числом состояний
3. Свойства замкнутости: регулярные языки замкнуты относительно многих операций (объединение, пересечение, дополнение, конкатенация, звезда Клини)

Примеры регулярных языков:

• содержитчётноечислоединиц (регулярный)
• начинаетсяс (регулярный)
• (не регулярный — нужен «счёт», недоступный FSA)

1.3 Операции над конечными автоматами

Одно из сильных свойств регулярных языков — их замкнутость относительно ряда операций: если применить такую операцию к регулярным языкам, результат снова регулярный. Для результирующих языков можно систематически построить FSA.

1.3.1 Дополнение

Задача: дан FSA , принимающий язык ; построить FSA для дополнения (все строки, не входящие в ).

Идея: чтобы принимать «противоположный» язык, инвертируем множество принимающих состояний (раньше принималось — теперь Reject, и наоборот).

Построение для полных FSA:

Для полного FSA автомат дополнения:

где (состояния, которые в не были принимающими).

Все прочие компоненты автомата не меняются — обновляется только множество принимающих состояний.

Пример: FSA над с состояниями :

• : , (нечётная длина)
• : те же переходы, но (чётная длина, включая )

Почему это верно? В полном FSA каждая строка заканчивается в некотором состоянии. Если оно было принимающим в , в хотим отвергать — делаем непринимающим; если было непринимающим — делаем принимающим.

Критично: полнота

Простой приём «поменять принимающие состояния» работает только для полных FSA. Почему?

В неполном FSA часть строк обрывается на неопределённом переходе и тем самым неявно отвергается. Поменяв только принимающие состояния, мы меняем судьбу лишь строк, которые полностью обработаны. Строки, отвергнутые из‑за неопределённости, этим приёмом не учитываются.

Построение для неполных FSA:

1. Сначала сделать FSA полным, добавив ловушку для всех неопределённых переходов
2. Затем поменять принимающие состояния:

Пример: неполный FSA: (принимающее), над .

Шаг 1: добавить ловушку :

• на b →
• на a →
• на a, b →

Шаг 2: дополнение. Было , значит .

Автомат дополнения принимает все строки, кроме тех, что начинаются с a и дальше содержат только b.

1.3.2 Пересечение

Задача: даны FSA и для языков и ; построить FSA для (строки, входящие в оба языка).

Идея: запускаем оба FSA параллельно на одной входной строке. Принимаем только если приняли бы оба автомата по отдельности.

Построение (прямое произведение):

Пусть

Тогда автомат пересечения:

где:

• (декартово произведение: пары состояний)
• (одновременный переход в обоих)
• (принимают оба)

Интуиция: состояние значит « в и в ». Читаем символ — обновляем обе компоненты. Принимаем, когда обе — в своих принимающих состояниях.

Пример:

принимает строки нечётной длины (над ):

• Состояния:
• Переходы: ,

принимает все строки (над ):

• Состояния:
• Переходы:

Произведение :

• Состояния:
• Переходы: ,
• ( и )

Принимаются строки нечётной длины (как у , так как всё пропускает).

Размер: при , в произведении состояний. Не все достижимы из начального — часто можно упростить, удаляя недостижимые.

1.3.3 Объединение

Задача: даны , для , ; построить FSA для (строки из хотя бы одного языка).

Построение:

Почти то же, что пересечение, но другое множество принимающих:

где:

• (хотя бы одна компонента принимающая)

Отличие от пересечения только в условии принятия: логическое ИЛИ () вместо И ().

Пример: те же , :

• (так как , обе пары подходят)
• Начальное принимающее — принимается даже
• Принимаются все строки (как у )

Альтернатива через законы де Моргана:

то есть «НЕ (НЕ И НЕ )» = принимается хотя бы одним.

1.3.4 Разность

Задача: построить FSA для (в , но не в ).

Построение:

Снова прямое произведение:

где:

• ( принимает и не принимает)

Интуиция: принимаем, когда « да» и « нет».

Пример: — нечётная длина, — все строки.

• (в , но не во «всём» — пусто)
• (нет с , так как и везде )

Обратный пример: (все строки кроме нечётной длины):

• (, )
• Принимаются строки чётной длины (включая )

1.4 Конечные преобразователи (FST)

Finite State Transducer (FST) обобщает FSA, добавляя выход: FSA лишь принимает или отвергает строки, FST преобразует входную строку в выходную.

1.4.1 Формальное определение

FST — кортеж:

где:

• — обычный FSA («компонента распознавания»)
• — выходной алфавит
• — выходная функция: на каждом переходе выдаётся строка выходных символов (возможно пустая)

Важно:

1. Преобразование только для принятых строк: если базовый FSA строку не принимает, выхода нет (или преобразователь «падает»)
2. На каждом переходе может быть выход: из по входу выдаётся
3. Выход может быть пустым ()

На диаграммах: переходы подписываются как , где — входной символ, — выходная строка.

1.4.2 Пример: удаление нечётных вхождений 0 и удвоение 1

Задача: FST над , который:

• принимает строки с чётным числом нулей
• на выходе:
  • каждое нечётное по счёту 0 удаляет (выход )
  • каждое чётное 0 оставляет (выход 0)
  • каждую 1 удваивает (выход 11)

Примеры:

• Вход: 010010 → Выход: 110110
• Вход: 00 → Выход: 0
• Вход: 000100011 → Выход: 011001111

Построение FST:

• Состояния:
  • (принимающее): «видели чётное число нулей»
  • : «видели нечётное число нулей»
• Переходы и выходы:
• Принимающие:

Как работает: чётность числа нулей кодируется состоянием; для 1 выход всегда 11; для 0 — или 0 в зависимости от нечётного/чётного вхождения.

1.4.3 Применения FST

• Текст: поиск-замена, орфография
• Обработка естественного языка: морфология (например walked → walk)
• Компиляторы: шаблоны исходного кода → целевой код
• Сжатие: кодирование/декодирование
• Замена по регулярным выражениям: в духе s/pattern/replacement/g

1.5 Свойства замкнутости регулярных языков

Семейство языков замкнуто относительно операции OP, если из следует .

Смысл замкнутости (closure): как у «замкнутой системы» — выполняя разрешённые операции, мы не выходим из класса. Для regular languages ряд операций снова даёт регулярный язык.

Регулярные языки замкнуты относительно:

1. Объединения: (прямое произведение)
2. Пересечения: (прямое произведение)
3. Дополнения: (смена принимающих в полном FSA)
4. Разности: (прямое произведение)
5. Конкатенации:
6. Звезды Клини:

Зачем это нужно:

1. Композиция: собираем сложные регулярные языки из простых
2. Доказательство регулярности: зная, что , регулярны, сразу знаем, что регулярен, не строя FSA
3. Компиляторы: комбинирование шаблонов для лексики

Пример: имеетчётноечислонулейилинечётноечислоединиц регулярен, потому что:

• имеетчётноечислонулей регулярен
• имеетнечётноечислоединиц регулярен
• по замкнутости относительно объединения

1.6 Практика: упрощение FSA

При построении FSA операциями пересечения/объединения часто появляются недостижимые состояния — те, в которые нельзя попасть из начального. Их можно удалить без смены языка.

Пример: при , в произведении 12 состояний, но не все пары достижимы из .

Алгоритм упрощения:

1. Пометить начальное состояние как достижимое
2. Итеративно помечать состояния, достижимые из уже помеченных по любому переходу
3. Удалить все непомеченные состояния и связанные с ними переходы

Это снижает размер автомата в реализациях.

---

2. Определения

• Полный FSA: конечный автомат, у которого всюду определена: для всех , значение задано.
• Неполный FSA (частичный FSA): автомат с частичной ; строки, доходящие до неопределённого перехода, автоматически отвергаются.
• Состояние-ловушка (ошибочное, сток): непринимающее состояние, добавляемое для дополнения неполного FSA; все бывшие «дыры» ведут в ловушку, в ловушке — петли по всем символам; войдя, не выходим; строки в ловушке отвергаются.
• Регулярный язык: , распознаваемый некоторым FSA; эквивалентно: существует FSA с .
• Дополнение языка: для над дополнение (или ) — все строки над , не входящие в : .
• Пересечение языков: (общий алфавит).
• Объединение языков: .
• Разность языков: .
• Прямое произведение автоматов: объединение и в один FSA с состояниями-парами , , ; параллельная симуляция на одном входе.
• Декартово произведение множеств: .
• Finite State Transducer (FST): расширение FSA выходной строкой; формально , — выходной алфавит, — выходная функция.
• Выходная функция (): в FST задаёт выходную строку (возможно ) при переходе из состояния по входному символу.
• Свойство замкнутости: семейство замкнуто относительно операции, если из результат операции снова в . Регулярные языки замкнуты относительно объединения, пересечения, дополнения, разности, конкатенации и звезды Клини.
• Недостижимое состояние: состояние, в которое нельзя попасть из начального ни по какой цепочке переходов; удаление не меняет распознаваемый язык.

---

3. Формулы

• Дополнение FSA (полный): для полного имеем ,
• Пересечение FSA (прямое произведение): для и автомат , где:
• Объединение FSA (прямое произведение): как пересечение, но
• Разность FSA (прямое произведение): как пересечение, но
• Законы де Моргана для языков: и

---

4. Примеры

4.1. Построение FST: прошедшее время → настоящее (Лаба 4, Задание 1)

Постройте полный FST над алфавитом , который:

• принимает только глаголы walked или talked
• переводит глагол в форму настоящего времени (убирает окончание ed)

Показать решение

Ключевая идея: FST читает посимвольно и выдаёт нужный выход. Для walked → walk выводим каждую букву, кроме финальных ed.

FST: пример морфологического перевода (англ.) walked/talked → walk/talk

1. Состояния:
   • (старт): ещё ничего не прочитано
   • : прочитано w или t
   • : wa или ta
   • : wal или tal
   • : walk или talk
   • : walke или talke
   • (принимающее): полностью walked или talked
   • : ошибка для неверного ввода
2. Переходы и выходы:
   • Из : w → выход w, в ; t → выход t, в ; иначе в ловушку
   • Из : a → a, в ; иначе ловушка
   • Из : l → l, в ; иначе ловушка
   • Из : k → k, в ; иначе ловушка
   • Из : e → , в (не выводим e)
   • Из : d → , в (не выводим d)
   • — принимающее
   • (непринимающее): любой «неверный» символ ведёт в ловушку с выходом ; из ловушки по каждому символу алфавита — петля в ловушку с выходом

Проверка:

• Вход: walked → Выход: walk ✓
• Вход: talked → Выход: talk ✓

Ответ: FST с состояниями и переходами как выше; на выходе все символы кроме финальных e и d.

4.2. Построение FST: стирание каждой второй a (Лаба 4, Задание 2)

Постройте полный FST над , который:

• принимает только строки, оканчивающиеся на b
• на выходе стирает каждое второе вхождение символа a

Показать решение

Ключевая идея: отслеживать чётность числа уже прочитанных a. На нечётных вхождениях выводить a, на чётных — . Символ b всегда выводить.

FST: каждая вторая a стирается, строка должна оканчиваться на b

1. Состояния:
   • (старт): чётное число a, последний символ не b
   • : нечётное число a, последний не b
   • (принимающее): чётное число a, строка оканчивается на b
   • (принимающее): нечётное число a, оканчивается на b
2. Переходы и выходы:
   • Из : a → выход a, в ; b → b, в
   • Из : a → , в ; b → b, в
   • Из : a → a, в ; b → b, остаёмся в
   • Из : a → , в ; b → b, остаёмся в
3. Принимающие:

Проверка:

• aaab → aab ✓
• aabb → abb ✓

Ответ: четыре состояния, чётность a и факт окончания на b, выходы как выше.

4.3. FSA для чётного числа единиц и нечётного числа нулей (Лаба 4, Задание 3)

Пусть .

Задача 1: полный FSA для содержитчётноечислоединиц

Задача 2: полный FSA для содержитнечётноечислонулей

Показать решение

Ключевая идея: двумя состояниями кодировать чётность счёта; чтение отслеживаемого символа переключает состояние.

Два FSA по чётности: чётное число единиц и нечётное число нулей

(a) FSA для чётного числа единиц ():

1. Состояния: (старт, принимающее) — чётное число единиц; — нечётное
2. Переходы: из : 0 — петля, 1 — в ; из : 0 — петля, 1 — в

Проверка: "" → ✓; 11 ✓; 101 ✓; 1 ✗

(b) FSA для нечётного числа нулей ():

1. Состояния: (старт) — чётное число нулей; (принимающее) — нечётное
2. Переходы: из : 1 — петля, 0 — в ; из : 1 — петля, 0 — в

Ответ: : , принимает ; : , принимает .

4.4. Комбинирование FSA: объединение, пересечение, разность (Лаба 4, Задание 4)

Используя и из Примера 4.3:

Задача 3: полный FSA для случая, когда принимает ИЛИ (объединение).

Задача 4: полный FSA, когда принимают оба (пересечение).

Задача 5: полный FSA, когда принимает и отвергает (разность).

Задача 6: дополнение для .

Показать решение

Ключевая идея: для объединения, пересечения и разности — прямое произведение; для дополнения — смена принимающих состояний у полного .

Прямое произведение: объединение, пересечение и разность

(Задача 3) Объединение:

1. Прямое произведение:
   • Начальное:
   • Переходы:
2. Принимающие (хотя бы одна компонента принимающая):

Ответ: FSA объединения имеет 4 состояния и 3 принимающих: .

(Задача 4) Пересечение:

1. То же произведение
2. Принимающие (обе компоненты принимающие):

Ответ: FSA пересечения — 4 состояния, одно принимающее: .

(Задача 5) Разность:

1. То же произведение
2. Принимающие ( принимает, отвергает):

Ответ: FSA разности — 4 состояния, одно принимающее: .

(Задача 6) Дополнение:

1. уже полон (есть переходы по всем входам)
2. Смена принимающих состояний: Исходно Дополнение

Ответ: у те же состояния и переходы, что у , но (принимается нечётное число единиц).

4.5. Дополнение неполного FSA (Лаба 4, Задание 5)

Постройте дополнение для неполного FSA над :

• (старт, принимающее): петля на 1, по 0 в
• : по 0 в ; переход по 1 не определён

Показать решение

Ключевая идея: сначала дополнить ловушкой, затем поменять принимающие.

Дополнение неполного FSA: сначала ловушка, затем дополнение

1. Ловушка : на 1 → ; петли на 0,1
2. Полный FSA: принимающее, нет (до дополнения)
3. Дополнение: было ,

Ответ: принимающие .

4.6. FSA для делимости на 2 и на 3 (Лаба 4, Задание 6)

; входит в оба языка.

Задача 1: полный FSA для двоичнаязаписьцелогоделящегосяна

Задача 2: полный FSA для двоичнаязаписьцелогоделящегосяна

Показать решение

Ключевая идея: в двоичной записи делимость на 2 — по последней цифре; на 3 — по остатку при чтении слева направо.

FSA: делимость на 2 и на 3 в двоичной записи

(a) Делимость на 2: число чётно тогда и только тогда, когда последняя цифра 0 (или пустая строка как 0).

1. (старт, принимающее): последняя цифра 0 или ещё не было цифр
2. : последняя цифра 1
3. Переходы: из на 0 — в , на 1 — в ; из на 0 — в , на 1 — петля

Проверка: ✓; 10 (=2) ✓; 11 (=3) ✗

(b) Делимость на 3: отслеживаем остаток при делении на 3. Читая двоичные цифры слева направо, обновляем остаток так: новыйостатокстарыйостатокцифра.

1. Состояния (остаток mod 3):

   • (старт, принимающее): остаток 0 (делится на 3)
   • : остаток 1
   • : остаток 2

2. Переходы: из состояния при чтении цифры новое состояние .

   Явно:

   • Из : 0 → (); 1 → ()
   • Из : 0 → (); 1 → ()
   • Из : 0 → (); 1 → ()

3. Принимающие:

Проверка: → в ✓; 11 (=3) ✓; 110 (=6) ✓; 10 (=2) ✗

Ответ: — 2 состояния (последняя цифра 0); — 3 состояния (остаток mod 3).

4.7. Комбинирование FSA делимости (Лаба 4, Задание 7)

По , из Примера 4.6:

Задача 3: полный FSA для пересечения (делится на 2 и на 3, т.е. на 6).

Задача 4: полный FSA для объединения (делится на 2 или на 3).

Задача 5: полный FSA: принимает и отвергает (делится на 2, но не на 3).

Показать решение

Ключевая идея: прямое произведение с нужным условием на принимающие пары.

Произведение автоматов для делимости на 2 и на 3

(Задача 3) Делимость на 6:

1. Состояния-пары: — 6 состояний. Начальное:
2. Принимающие (делятся на 2 и на 3):

Ответ: FSA для делимости на 6 имеет 6 состояний и одно принимающее: .

(Задача 4) Делимость на 2 или 3:

1. То же множество пар состояний
2. Принимающие (делится на 2 ИЛИ на 3):

Ответ: 6 состояний, 4 принимающих.

(Задача 5) Делится на 2, но не на 3:

1. То же произведение
2. Принимающие (на 2 да и на 3 нет):

Ответ: 6 состояний, два принимающих: и .

4.8. Сложное прямое произведение (Лаба 4, Задание 8)

Пусть и — полные FSA над алфавитом :

:

• Состояния: (старт), , (принимающее)
• Переходы: — петля на b, по a в ; — петля на a, по b в ; по b в

:

• Состояния: (старт), , (принимающее)
• Переходы: — петля на a, по b в ; по a в , по b в ; — петли на a и b

Нарисуйте полные FSA, принимающие:

(i)
(ii)
(iii)

Показать решение

Ключевая идея: прямое произведение; принимающие состояния задаются по смыслу операции.

(i) Объединение:

1. Пары состояний: — 9 состояний. Начальное:

2. Принимающие (хотя бы одна компонента принимающая):

   Явно:

3. Переходы: для всех пар и символов

Ответ: FSA из 9 состояний, 5 принимающих (все пары, где или ).

(ii) Пересечение:

1. То же произведение
2. Принимающие (обе компоненты принимающие):

Ответ: 9 состояний, одно принимающее: .

(iii) Разность:

1. То же произведение
2. Принимающие ( принимает, отвергает):

Ответ: 9 состояний, два принимающих: и .

4.9. От диаграммы состояний к таблице переходов (Туториал 4, Пример 1)

Дан FSA в виде диаграммы переходов; постройте таблицу переходов.

Три состояния: (старт), , (принимающее), алфавит . Переходы:

• ,
• ,
• ,

Показать решение

Ключевая идея: таблица переходов — другой способ задать FSA: строки — состояния, столбцы — символы алфавита, в ячейках — состояние назначения.

1. Структура таблицы:
   • Строки: по одной на каждое состояние ()
   • Столбцы: по одному на каждый символ ()
   • Начальное состояние помечают , принимающие —
2. Заполнение по диаграмме:
   • Из : a → , b →
   • Из : a → , b →
   • Из : a → , b →

Таблица переходов:

	a	b

Ответ: заполненная таблица приведена выше.

4.10. Дополнение неполного FSA до полного (Туториал 4, Пример 2)

Неполный FSA над :

• (старт) (принимающее)
• (принимающее) (петля)

Переходы и не определены. Сделайте автомат полным.

Показать решение

Ключевая идея: добавить состояние-ловушку и направить в неё все ранее неопределённые переходы.

1. Неопределённые переходы: ,
2. Добавить ловушку (непринимающее)
3. Доопределить:
4. Петли ловушки: ,

Полный FSA:

• Состояния: (старт), (принимающее), (ловушка, непринимающее)
• Переходы:
  • ,
  • ,
  • ,

Ответ: полный FSA с ловушкой , куда ведут все бывшие «дыры».

4.11. Дополнение полного FSA (Туториал 4, Пример 3)

Полный FSA над :

Он принимает строки с нечётным числом символов a. Постройте .

Показать решение

Ключевая идея: у полного FSA дополнение — смена принимающих и непринимающих состояний.

1. Исходные принимающие:
2. Дополнение:

Переходы те же; меняется только на .

Проверка:

• принимает: a, aaa, aaaaa, … (нечётная длина)
• принимает: , aa, aaaa, … (чётная длина, включая ноль)

Ответ: принимает строки с чётным числом a.

4.12. Дополнение неполного FSA (Туториал 4, Пример 4)

Неполный FSA над :

• (старт) (принимающее)
• (петля)

Постройте автомат для дополнения.

Показать решение

Ключевая идея: сначала сделать автомат полным, затем взять дополнение.

1. Ловушка : , , петли на ,
2. Полный FSA: состояния ; принимающие до дополнения
3. Дополнение:

Автомат дополнения:

• Состояния: (старт, принимающее), (непринимающее), (принимающее)
• Переходы как у дополненного автомата
• Принимающие:

Ответ: дополнение принимает все строки, кроме вида при .

4.13. Пересечение двух FSA (Туториал 4, Пример 5)

Дано:

• , где , (нечётная длина)
• , где (все строки)

Постройте .

Показать решение

Ключевая идея: прямое произведение; принимающие — пары, в которых обе компоненты принимающие.

2. Начальное:
3. Переходы :

Произведение:

Ответ: пересечение принимает строки нечётной длины (как , так как принимает всё).

4.14. Пересечение более сложных FSA (Туториал 4, Пример 6)

Два FSA над :

:

• Состояния: (старт), , (принимающее),
• Переходы: , ; , ; — петли на ; — петли на

:

• Состояния: (старт), , (принимающее)
• Переходы: , ; , ; — петли на

Постройте и упростите, удалив недостижимые состояния.

Показать решение

Ключевая идея: полное произведение, затем выделение достижимых состояний.

1. Полное произведение: — состояний. Начало . Принимающие:

2. Примеры переходов:

   • Из по a:
   • Из по b:
   • Из по a: — достижение принимающего состояния

3. Достижимость из : чтобы попасть в в , нужна цепочка ; в в — (далее петлит по всем символам)

   Путь для строки aaba: ✓

4. После удаления недостижимых остаётся упрощённый автомат пересечения.

Ответ: упрощённое пересечение принимает строки, которые одновременно доводят до и до ; одна из кратчайших принимаемых строк — aaba.

4.15. Объединение двух FSA (Туториал 4, Пример 7)

Используя те же и , что в примере 4.13 (нечётная длина и все строки), постройте .

Показать решение

Ключевая идея: то же произведение; принимающие — пары, где хотя бы одна компонента принимающая.

1. Состояния и переходы как у пересечения:

   • Начало
   • ,

2. . Так как и во всех достижимых парах , условие выполняется всегда.

   Следовательно — оба состояния принимающие; начальное принимающее, значит принимается . Фактически принимаются все строки.

Ответ: принимает все строки над (как ).

4.16. Разность двух FSA (Туториал 4, Пример 8)

Найдите , где — нечётная длина, — все строки (как выше).

Показать решение

Ключевая идея: принимающие — пары, где первая компонента принимающая, а вторая нет.

1. Произведение: , начало
2. . Здесь , .
   • Для : , но — не подходит
   • Для : — не подходит
   • Итог:

Ответ: — пустой язык: всё, что в , уже в .

4.17. Разность двух FSA (Туториал 4, Пример 9)

Найдите (все строки минус нечётная длина).

Показать решение

1. : нужно и .
   • : ✓, ✓ — принимающее
   • : ✗ — не принимающее
   • Итог:

Ответ: принимает строки чётной длины (включая ).