W3. Конечные автоматы (FSA), формальные определения, распознавание языков
1. Краткое содержание
1.1 Историческая справка
Теория конечных автоматов сложилась в 1940–1960‑е годы благодаря работам нескольких исследователей:
- Уоррен Маккаллок и Уолтер Питтс (1943): опубликовали первую математическую модель нейронной сети, используя структуры, близкие к конечным автоматам; показали, что нейроны, выполняющие логические операции, можно моделировать как конечные автоматы.
- Стивен Клини (1951): формализовал регулярные события и доказал эквивалентность конечных автоматов и регулярных выражений, заложив алгебраический фундамент теории.
- Эдвард Ф. Мур (1956): ввёл машину Moore — преобразователь, выход которого зависит только от текущего состояния.
- Джордж Х. Мили (1955): ввёл машину Mealy — преобразователь, выход которого зависит и от текущего состояния, и от текущего входного символа.
- Майкл О. Рабин и Дана Скотт (1959): опубликовали статью «Finite Automata and Their Decision Problems», ввели недетерминированные конечные автоматы (NFA) и доказали их эквивалентность детерминированным. За эту работу им присудили премию Тьюринга в 1976 году.
Эти результаты закрепили роль FSA как центральной модели в теоретической информатике, конструировании компиляторов и теории формальных языков.
1.2 FSA и машина Тьюринга
Машина Тьюринга — существенно более мощная модель вычислений: у неё есть бесконечная лента как неограниченная память, поэтому она может решать задачи, недоступные FSA. Однако эта общность имеет практическую цену:
- FSA обладают лишь конечной памятью (текущее состояние кодирует всю доступную информацию). Они просты, быстры и удобны для распознавания шаблонов в потоках данных.
- Машины Тьюринга в принципе требуют бесконечной памяти, что нереализуемо в физическом оборудовании.
Для многих инженерных задач — лексический анализ, проверка протоколов, аппаратные контроллеры, фильтрация сетевых пакетов — распознаваемые шаблоны регулярны: не нужно считать до произвольной глубины или помнить неограниченную историю. FSA достаточно и гораздо эффективнее. Неограниченная мощность машины Тьюринга для таких задач излишня и лишь усложняет решение.
Ключевой принцип: используйте простейшую модель вычислений, достаточную для задачи. Для регулярных шаблонов уместны FSA.
1.3 Что такое конечный автомат?
FSA (Finite State Automaton) — математическая модель вычислений для распознавания шаблонов и обработки последовательностей символов; ту же модель в узком смысле называют также FSM (Finite State Machine). Это одна из простейших и при этом очень важных моделей. FSA — абстрактная машина, которая:
- Начинает работу в выделенном start state — начальном состоянии.
- Читает входные символы по одному из alphabet
- Совершает transitions между states в зависимости от входного символа и текущего состояния.
- Даёт ответ Accept или Reject в зависимости от того, оказались ли мы в accepting (final) state — принимающем состоянии.
Можно думать об FSA как об очень простом компьютере с фиксированным объёмом памяти — ровно настолько, чтобы помнить, в каком из конечного числа состояний он сейчас находится. Произвольную информацию он хранить не может, но может распознавать шаблоны, задаваемые регулярными правилами.
1.4 Примеры из практики
FSA повсюду в информатике:
- Торговые автоматы: состояния соответствуют внесённой сумме; каждая монета переводит в новое состояние.
- Светофоры: состояния — красный, жёлтый, зелёный; переходы задаются временем или датчиками.
- Лексические анализаторы (lexer): в компиляторах FSA выделяют лексемы — идентификаторы, ключевые слова, числа в исходном коде.
- Персонажи в играх: поведение вроде «блуждание», «преследование», «бегство» — состояния с переходами по событиям.
- Разбор текста: распознавание шаблонов в документах.
- Анализ протоколов: проверка допустимости последовательностей сетевых сообщений.
1.5 Неформальное введение с примерами
Пример: турникет (вход в метро)
Представьте турникет:
- Состояния: Заперто (пройти нельзя) и Открыто (можно пройти)
- Начальное состояние: Заперто
- Принимающее состояние: Заперто (система в корректном состоянии)
- Алфавит: {Толкнуть, Монета}
- Переходы:
- Из Заперто: Монета → Открыто; Толкнуть → остаёмся в Заперто.
- Из Открыто: Толкнуть → Заперто (прошли и снова заперли); Монета → остаёмся в Открыто.
Этот простой FSA полностью описывает поведение турникета.
1.6 Формальное определение конечного автомата
Детерминированный конечный автомат (DFA) формально задаётся как 5‑ка:
где:
З а п е р т о О т к р ы т о
Детерминированность означает: для каждой пары «состояние, символ» существует ровно одно следующее состояние. В недетерминированных FSA (NFA) возможны несколько вариантов следующего состояния; здесь основной фокус — на DFA.
1.7 Чтение строки автоматом FSA
Для строки (последовательности символов)
- Старт в начальном состоянии
- Читаем
- Читаем
- Продолжаем, пока не прочитаны все символы
- Если конечное состояние лежит в
1.8 Расширенная функция переходов
Чтобы формализовать обработку целой строки, вводят расширенную функцию переходов
Она обрабатывает всю строку (не один символ). Задаётся рекурсивно:
- База:
- Шаг: для любой строки
Так формализуется пошаговый процесс из предыдущего пункта.
1.9 Принятие строк и языки
- Строка
- Строка отвергается FSA
- Язык, распознаваемый
- Язык
1.10 Полные и неполные FSA
- Полный FSA:
- Неполный FSA:
Чтобы сделать неполный FSA полным, обычно добавляют состояние‑ловушку (или ошибочное состояние): все ранее неопределённые переходы ведут в него. Ловушка не принимающая; попав в неё, автомат обычно остаётся там (часто с петлёй на все символы).
1.11 Графическое представление
FSA изображают диаграммами состояний:
- Состояния — круги (или скруглённые прямоугольники)
- Стрелка «ниоткуда» указывает на начальное состояние
- Принимающие состояния — двойные круги
- Переходы — стрелки с подписями символов (или множеств символов)
- Петля — переход из состояния в себя
1.12 Детерминированные и недетерминированные FSA
- DFA: для каждой пары «состояние, символ» ровно одно следующее состояние — как в формальном определении выше.
- NFA: для пары «состояние, символ» может быть ноль, одно или несколько следующих состояний; допускаются переходы по пустой строке (
NFA удобнее в записях, но любой NFA эквивалентен некоторому DFA. В курсе основной упор — на детерминированные FSA.
1.13 Конечные и бесконечные языки
Конечные языки — множества из конечного числа строк. Например,
Бесконечные языки содержат бесконечно много строк. Не все бесконечные языки регулярны, но многие — да. Два типичных регулярных бесконечных примера:
- Строки, начинающиеся с «0»:
- Язык
Напротив, язык
1.14 Применения в компиляторах
FSA критичны для лексического анализа — первой фазы компиляции:
- Lexer (сканер) читает исходный код посимвольно
- С помощью FSA выделяются лексемы: идентификаторы, ключевые слова, числа, операторы, пунктуация
- Идентификатор в большинстве языков начинается с буквы, за которой следует ноль или больше букв и цифр
- FSA распознаёт шаблон: начальное состояние → (буква) → принимающее → петля (буква/цифра)* → принимающее
Генератор лексеров вроде lex по регулярным выражениям (описывающим регулярные языки) автоматически строит FSA и код сканера.
1.15 Конечные преобразователи
Конечный преобразователь состояний (FST, Finite State Transducer) — расширение FSA, которое помимо принятия/отклонения входа выдаёт выход. У FST есть:
- Входная лента с символами входного алфавита
- Выходная лента, куда пишутся символы выходного алфавита
- Переходы с метками
FST применяют для:
- компиляции в целевой код
- перевода между языками
- сжатия и распаковки
- замены шаблонов в тексте
Формально FST — 7‑ка:
где:
Отношение преобразования, вычисляемое
В общем случае
1.16 Абстракция и коммуникация
Важнейший навык информатика — и в целом инженера — свободно переходить между двумя уровнями описания:
- Неформальный (интуитивный): рассказ или рисунок, передающий замысел системы без полной математической строгости. Пример: «турникет открывается, когда бросаешь монету».
- Формальный (математический): жёсткая спецификация в общепринятой нотации, однозначная и пригодная для механических рассуждений. Пример: 5‑ка
Умение переводить между уровнями — абстракция — позволяет из неформальных требований заказчика получать корректный, проверяемый код. Без абстракции идеи остаются размытыми; без опоры на формализм математические объекты отрываются от реальности.
Связь с риторическим треугольником Аристотеля. Убедительное изложение технических идей требует баланса трёх элементов:
| Элемент | Значение | В техническом контексте |
|---|---|---|
| Logos (логос) | Логическое содержание и структура аргумента | Формальное определение, доказательство, алгоритм |
| Ethos (этос) | Авторитет и доверие к говорящему | Ссылки на установленные результаты, аккуратная нотация |
| Pathos (патос) | Эмоциональная связь, учёт аудитории | Наглядные примеры, аналогии, мотивация |
Сильное техническое объяснение сочетает logos (строгий аргумент), ethos (опора на теорию) и pathos (примеры и мотивация для читателя). Понимание этого баланса помогает формулировать спецификации, проекты и доказательства для коллег, заказчиков и средств формальной верификации.
2. Определения
- Алфавит (
- Строка: последовательность нуля или более символов алфавита. Пустая строка обозначается
- Состояние: конфигурация FSA; в каждый момент автомат ровно в одном состоянии.
- Начальное состояние (
- Принимающее состояние (конечное): если после чтения всего входа FSA в таком состоянии, строка принимается. Множество принимающих состояний —
- Функция переходов (
- Полный FSA:
- Неполный FSA:
- Расширенная функция переходов (
- Язык: множество строк над алфавитом; может быть конечным или бесконечным.
- Регулярный язык: язык, распознаваемый некоторым конечным автоматом.
- DFA: FSA, в котором из каждого состояния по каждому символу не более одного исходящего перехода (нет недетерминизма).
- NFA: FSA, где по одному символу возможно несколько исходящих переходов или есть
- Состояние‑ловушка (ошибочное): непринимающее состояние для дополнения неполного FSA до полного; все «дыры» в
- FST: FSA с выходной лентой и выходной функцией; задаёт преобразование входных строк в выходные.
- Lexer (сканер): программа, читающая текст посимвольно и с помощью FSA выделяет лексемы (идентификаторы, ключевые слова, числа и т.д.).
3. Формулы
- Функция переходов:
- Расширенная функция (база):
- Расширенная функция (рекурсия):
- Принятие строки:
- Язык FSA:
- Неполный автомат:
4. Примеры
4.1. Турникет: формальное описание (Лаба 3, Пример 1)
Смоделируйте турникет метро как FSA. Два состояния: Locked (Заперто) и Unlocked (Открыто). Изначально Locked. Типовая последовательность: Coin в Locked
Показать решение
Шаг 1: компоненты
- Состояния: Заперто и Открыто
- Алфавит: {Толкнуть, Монета}
- Начальное состояние: Заперто (нормальное «закрытое» состояние)
- Принимающее состояние: Заперто (транзакция завершена корректно)
Шаг 2: переходы
- Заперто + Толкнуть → Заперто
- Заперто + Монета → Открыто
- Открыто + Толкнуть → Заперто
- Открыто + Монета → Открыто
Шаг 3: формальное определение
где:
З а п е р т о О т к р ы т о Т о л к н у т ь М о н е т а
| Толкнуть | Монета | |
|---|---|---|
| Заперто | Заперто | Открыто |
| Открыто | Заперто | Открыто |
З а п е р т о З а п е р т о
Шаг 4: примеры строк
- «Толкнуть–Толкнуть»: Заперто →Толкнуть→ Заперто →Толкнуть→ Заперто → ПРИНЯТЬ
- «Монета»: Заперто →Монета→ Открыто (не принимающее) → ОТВЕРГНУТЬ
- «Толкнуть–Монета–Монета–Монета–Толкнуть»: в конце Заперто → ПРИНЯТЬ
Этот FSA принимает в точности те последовательности, в которых каждая Монета когда‑то сопровождается (впоследствии) Толкнуть.
4.2. Простая задача: какую строку нельзя принять? (Лаба 3, Задание 1)
Рассмотрите FSA ниже. Какую из строк этот автомат не может принять?
Описание FSA:
- Состояния:
- Переходы:
Какие из строк отвергаются?
- «ac»
- «aaac»
- «aaacda»
- «aaacdb»
Показать решение
Ключевая идея: прослеживаем состояния по символам. Неопределённый переход — немедленный отказ. Если вход кончился не в принимающем состоянии — отказ.
Шаг 1: структура
- Из
- Из
- Из
- Из
Из
Шаг 2: строка «ac»
- Старт:
- «a»:
- «c»:
- Конец:
Шаг 3: «aaac»
Шаг 4: «aaacda»
- …
- Конец:
Шаг 5: «aaacdb»
- …
Ответ: наиболее явный отказ — (c) «aaacda» (конец в
4.3. Двоичные числа, начинающиеся с 1 (Лаба 3, Задание 2)
Постройте полный FSA для языка:
Примеры: «1», «10», «11», «100», «101», …
Показать решение
Ключевая идея: нужно распознать строки, у которых первый символ — 1. После первой единицы мы в принимающем состоянии; любые дальнейшие 0 и 1 сохраняют приём.
Шаг 1: состояния
Шаг 2: переходы
Из
Из
Из
Шаг 3: формальное определение
где
| 0 | 1 | |
|---|---|---|
Шаг 4: проверка
- «1», «10», «101» → ПРИНЯТЬ ✓
- «0», «01» → ОТВЕРГНУТЬ ✓
Автомат полный: из каждого состояния есть переходы по 0 и 1.
4.4. Двоичные строки, не начинающиеся с 1 (Лаба 3, Задание 3)
Постройте полный FSA для:
Примеры: «», «0», «00», «01», «001», …
Показать решение
Ключевая идея: язык включает пустую строку (она «не начинается с 1») и все строки, у которых первый символ 0. После первого 0 принимаем любое продолжение.
Шаг 1: состояния
Шаг 2–3:
| 0 | 1 | |
|---|---|---|
Шаг 4: «», «0», «01» → ПРИНЯТЬ; «1», «10» → ОТВЕРГНУТЬ ✓
4.5. Любая 0 сразу за которой есть хотя бы одна 1 (Лаба 3, Задание 4)
Полный FSA для:
Примеры: «010111», «1111», «01110111011». Недопустимы 0 в конце строки и подстрока «00».
Показать решение
Ключевая идея: каждая 0 в строке должна быть непосредственно сопровождена хотя бы одной 1. Значит, запрещены: 0 в самом конце строки и пара «00» подряд.
Шаг 1: состояния
Шаг 2: переходы
Из
Из
Из
Шаг 3: формальное определение
где
| 0 | 1 | |
|---|---|---|
Шаг 4: проверка
- «1111»: остаёмся в
- «010111»:
- «01110111011»: аналогично заканчиваем в
- «10»:
- «100»:
4.6. Двоичные строки, оканчивающиеся на 00 (Лаба 3, Задание 5)
Полный FSA для:
Примеры: «00», «100», «1100», «00100».
Показать решение
Ключевая идея: отслеживать, что два последних символа — оба 0. Нужны состояния: (1) на конце нет «хвоста» из нулей подряд, (2) на конце один 0, (3) на конце «00» (принимаем).
Шаг 1: состояния
Шаг 2: переходы
Из
Из
Из
Шаг 3: формальное определение
где
| 0 | 1 | |
|---|---|---|
Шаг 4: проверка
- «00», «100», «1100» → ПРИНЯТЬ ✓
- «101» → ОТВЕРГНУТЬ ✓
4.7. Ровно три нуля в двоичной строке (Лаба 3, Задание 6)
Полный FSA для:
Примеры: «000», «0001», «1010100», «11001001».
Показать решение
Ключевая идея: нужно «считать» число нулей. Вводим состояния: видели 0, 1, 2, 3 нуля; больше трёх нулей — ловушка.
Шаг 1: состояния
Шаг 2: переходы
Чтение 1 не меняет «счётчик» нулей (остаёмся в том же состоянии). Чтение 0 увеличивает счёт до перехода в
Шаг 3: формальное определение
где
| 0 | 1 | |
|---|---|---|
Шаг 4: проверка
- «000»:
- «0001»:
- «1010100»: …
- «11001001»: …
4.8. Каждая a сразу за которой идёт bb (Лаба 3, Задание 7)
Полный FSA для:
Примеры: «», «b», «bb», «abbabb», «bbbabbb».
Показать решение
Ключевая идея: после каждой «a» должны сразу идти «b» и ещё «b» — подстрока «abb». Иные «a» допустимы только в рамках этого же правила.
Шаг 1: состояния
Шаг 2: переходы
Из
Из
Из
Из
Шаг 3: формальное определение
| a | b | |
|---|---|---|
Шаг 4: проверка
- «», «b», «bb», «abb», «abbabb» → ПРИНЯТЬ ✓
- «ab»: конец в
- «aba»: уход в
4.9. Оканчивается на b и нет подстроки aa (Лаба 3, Задание 8)
Примеры: «b», «ab», «bab», «abb», «abab», «babab». Не подходят: «a», «aa», «baa», «aba» (конец «a»), «aab» (есть «aa»).
Показать решение
Ключевая идея: выполнить одновременно два условия: (1) подстроки «aa» нигде нет; (2) строка заканчивается на «b». Отслеживаем: только что видели «a» или «b»; при появлении «aa» уходим в ловушку.
Шаг 1: состояния
Принимающее только
Шаг 2: переходы
Из
Из
Из
Шаг 3: формальное определение
| a | b | |
|---|---|---|
Шаг 4: проверка
- «b», «ab», «bab», «abb», «abab» → ПРИНЯТЬ ✓
- «a», «aa», «aab», «aba» → ОТВЕРГНУТЬ ✓
4.10. Содержит подстроку abbaab (Лаба 3, Задание 9)
Примеры: «abbaab», «aabbaab», «ababbaab».
Показать решение
Ключевая идея: накапливать совпадение с префиксом «abbaab». При «срыве» нужно корректно откатываться к подходящему префиксу. После полного совпадения остаёмся в принимающем состоянии при любых дальнейших символах.
Шаг 1: состояния
Шаг 2: переходы (суть)
Из
Из
Из
Из
Из
Из
Из
Шаг 3: таблица
| a | b | |
|---|---|---|
Шаг 4: проверка
- «abbaab»:
- «aabbaab»: через
4.11. Чётное число a и чётное число b (Лаба 3, Задание 10)
Примеры: «», «aabb», «abab», «aabbab», «baba» (по две «a» и две «b»).
Показать решение
Ключевая идея: независимо отслеживать чётность счётчиков «a» и «b» — четыре комбинации чёт/нечёт.
Шаг 1: состояния
Шаг 2: переходы
Каждая «a» меняет чётность «a»; каждая «b» — чётность «b».
Из
Из
Из
Из
Шаг 3: формальное определение
| a | b | |
|---|---|---|
Шаг 4: проверка
- «»: в
- «aabb», «abab» → ПРИНЯТЬ ✓
- «a», «aab» → ОТВЕРГНУТЬ ✓
4.12. Двоичная запись, делимость на 5, начинается с 1 (Лаба 3, Задание 11)
Примеры: «101» (5), «1010» (10), «1111» (15), «11001» (25).
Показать решение
Ключевая идея: число делится на 5 тогда и только тогда, когда остаток по модулю 5 равен 0. Читая биты слева направо, обновляем остаток: если сейчас остаток
Шаг 1: состояния
Шаг 2: переходы
Для состояний с остатком
Из
Из
Из
Из
Из
Из
Из
Шаг 3: формальное определение
| 0 | 1 | |
|---|---|---|
Шаг 4: проверка
- «101» (5):
- «1010» (10), «1111» (15) → ПРИНЯТЬ ✓
- «1100» (12) → ОТВЕРГНУТЬ ✓
4.13. Длина ≥ 2 и два последних символа совпадают (Лаба 3, Задание 12)
Примеры: «00», «11», «100», «011», «0100».
Показать решение
Ключевая идея: хранить последние два символа и обеспечить
Шаг 1 (черновик):
Шаг 1 (уточнение):
Шаг 2: переходы
Из
Из
Из
Из
Из
Из
Из
Шаг 3: формальное определение
| 0 | 1 | |
|---|---|---|
Шаг 4: проверка
- «00», «11», «100», «0100» → ПРИНЯТЬ ✓
- «01», «0» → ОТВЕРГНУТЬ ✓
4.14. Подстрока abc встречается нечётное число раз (Лаба 3, Задание 13)
Показать решение
Ключевая идея: отдельно хранить чётность уже завершённых «abc» и длину текущего префикса «abc» (0, 1 или 2 символа). Завершение «abc» меняет чётность и сбрасывает прогресс.
Шаг 1: состояния
Шаг 2: формальное определение
| a | b | c | |
|---|---|---|---|
Шаг 3: проверка
- «abc»:
- «abcabc»: после второго «abc» возвращаемся в
- «abcabcabc»: три раза → снова
4.15. Шариковая игрушка как FSA (Лаба 3, Домашнее задание 1)
Смоделируйте игрушку со шариком как полный FSA. Два входа (A и B), два выхода (C и D). Три рычага X1, X2, X3:
- шарик входит в A или B;
- X1 под A, X3 под B, X2 в центре;
- каждый рычаг при проходе шарика переворачивается для следующего;
- принятие — выход в D (выход в C — отказ).
Показать решение
Ключевая идея: у каждого рычага два положения (лево/право); шарик отклоняется в сторону, зависящую от положения; после прохода рычаг меняет сторону. Состояние системы — вектор из трёх положений.
Шаг 1: траектории
- Из A шарик попадает на X1. Если X1 в положении L — уходит в C; если R — идёт к X2.
- Из B шарик попадает на X3. Если X3 в L — идёт к X2; если R — сразу в D.
- С X2: L → C, R → D.
Каждый рычаг, через который прошёл шарик, переворачивается.
Шаг 2: состояния
Шаг 3–5: переходы по A и B (см. пошаговый разбор в англ. лекции): из каждой тройки и входа A или B однозначно получаем новую тройку и выход C/D;
Шаг 6–7: формальное определение
| A | B | |
|---|---|---|
Шаг 8: примеры
- «A»:
- «AB»:
- «BA»:
4.16. Выключатель света (Лекция 3, Пример 1)
FSA переключателя: щелчок чередует состояния Вкл и Выкл.
Показать решение
Ключевая идея: два состояния и чередование по входу «переключить».
В к л В ы к л В ы к л В к л - Вкл + T → Выкл; Выкл + T → Вкл.
В к л В ы к л В ы к л В к л
Проверка: «T» → ПРИНЯТЬ; «TT» → ОТВЕРГНУТЬ; «TTT» → ПРИНЯТЬ — принимается нечётное число переключений.
4.17. ИИ в игре: призрак Pac-Man (Лекция 3, Пример 2)
Показать решение
Ключевая идея: режимы поведения как состояния FSA.
- Состояния: Блуждание; Преследование; Бегство (после энерджайзера); Возврат на базу.
- Переходы (события): Блуждание → Преследование: «заметил Pac-Man»; Преследование → Бегство: «Pac-Man съел энерджайзер»; Бегство → Блуждание: «энерджайзер кончился»; Преследование → Возврат: «съеден Pac-Man»; Возврат → Блуждание: «достигнут центр базы».
- Начальное: Блуждание. Принимающие зависят от дизайна игры.
Ответ: FSA из четырёх состояний с событийными переходами; в реальных играх логика сложнее, но идея конечных состояний та же.
4.18. Компилятор: идентификатор Pascal (Лекция 3, Пример 3)
FSA для идентификаторов Pascal: первая — буква, далее ноль или больше букв/цифр.
Показать решение
Состояния 3.qmd, §4.18.
«count», «var123» → ПРИНЯТЬ; «123var» → ОТВЕРГНУТЬ ✓
4.19. Простой FSA: распознаёт только «ba» (Туториал 3, Пример 1)
Постройте FSA, принимающий только строку «ba».
Показать решение
Ключевая идея: цепочка состояний по позициям целевой строки.
- Состояния:
- Переходы:
- Проверка: «ba» → ПРИНЯТЬ ✓; «ab»: из
Ответ: три состояния и линейный путь
4.20. Простой FSA: распознаёт только «aba» (Туториал 3, Пример 2)
Показать решение
Ключевая идея: как в примере 4.19, по одному состоянию на каждый прочитанный префикс.
- Состояния:
- Переходы:
- Проверка: «aba» → ПРИНЯТЬ ✓
Ответ: четыре состояния в линейной цепочке «aba».
4.21. Полный FSA для «ba» с ловушкой (Туториал 3, Пример 3)
Дополните автомат для «ba» до полного, добавив ловушку.
Показать решение
Ключевая идея: все ранее неопределённые переходы направить в новое непринимающее состояние
- Исходно:
- Добавляем
- Каждое состояние имеет исходящие переходы по всем символам алфавита
Ответ: четыре состояния,
4.22. Полный FSA для «aba» с ловушкой (Туториал 3, Пример 4)
Показать решение
Ключевая идея: та же схема, состояние‑ловушка
- Из
- Из
- Из
- Из
- Из
Ответ: пять состояний:
4.23. FSA с несколькими принимающими:
Показать решение
Ключевая идея: отдельное принимающее состояние для каждой допустимой строки (или общая структура с двумя «успехами»).
- Состояния:
- Переходы:
Проверка: «a» и «aba» → ПРИНЯТЬ; «ab» → ОТВЕРГНУТЬ ✓
4.24. Язык с пустой строкой:
Показать решение
Ключевая идея: сделать начальное состояние принимающим, чтобы принять
Проверка:
4.25. FSA, принимающий все строки над
Показать решение
Ключевая идея: одно принимающее состояние с петлями на все символы.
- Одно состояние
Поскольку
4.26. FSA для пустого языка (Туториал 3, Пример 8)
Показать решение
Ключевая идея: ни одно принимающее состояние недостижимо из начального (или
- Например,
- Ни для какой строки конечное состояние не лежит в
Ответ: начальное непринимающее, принимающие недостижимы.
4.27. Бесконечный регулярный язык: строки, начинающиеся с 0 (Туториал 3, Пример 9)
Постройте FSA для
Показать решение
Ключевая идея: после проверки первого символа «всё остальное» остаётся в принимающем состоянии — язык бесконечен, но регулярен.
- Из
Проверка: «0», «01101» → ПРИНЯТЬ; «1000» → ОТВЕРГНУТЬ ✓
Ответ: три состояния; после первого нуля остаёмся в принимающем навсегда.
4.28. Язык повторений «ab» (Туториал 3, Пример 10)
Постройте FSA для
Показать решение
Ключевая идея: чередование «a» и «b»; после полной пары «ab» возврат в принимающее
- Из
Проверка:
4.29. Нерегулярные языки (Туториал 3, Пример 11)
Важная мысль: не всякий бесконечный язык регулярен. Рассмотрим
Показать решение
Ключевая идея: язык требует счёта с неограниченным запасом значений; конечной памяти FSA недостаточно.
Почему не FSA:
- Конечное число состояний — конечный «объём памяти».
- Чтобы проверить
- Pigeonhole principle: после
Ответ: язык не регулярен; нужны более сильные модели — PDA (магазинная память) или машина Тьюринга.