Информатика · объяснение и практика
Как конечный автомат хранит только нужное состояние истории
Создаём автомат чётности единиц, выписываем переходы и объясняем, какую информацию о прочитанной части строки можно забыть.

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
Конечный автомат читает строку по символу и сохраняет одно из конечного числа состояний. Состояние должно содержать всю информацию о прошлом, необходимую для дальнейшего решения. Приём строки определяется состоянием после чтения последнего символа.
Хранить количество целиком необязательно
Нужно принимать двоичные строки с чётным числом единиц. Полное число уже прочитанных единиц может расти без ограничений, но для ответа важна только чётность. Создадим два состояния: Ч означает чётное число единиц, Н — нечётное. Начальное состояние Ч, потому что до чтения строки единиц ноль.
При чтении нуля остаёмся в прежнем состоянии: число единиц не меняется. При чтении единицы переключаемся между Ч и Н. Принимающим сделаем Ч. Так для каждого состояния и каждого символа алфавита задан ровно один следующий шаг — это детерминированный конечный автомат.
Пример
Строка 10101 проходит состояния Ч→Н→Н→Ч→Ч→Н и отвергается.
В ней три единицы. Строка 1010 закончилась бы в Ч и была бы принята: добавленная единица меняет именно чётность.
Переход в принимающее состояние ещё не конец ввода
Во время чтения 10101 автомат временно оказывается в Ч. Это не означает, что вся строка принята: остающиеся символы способны изменить состояние. Для распознавания целой строки решающим является только состояние после полного ввода. Поиск подходящего фрагмента внутри длинного текста — другая постановка.
Пустая строка сразу заканчивается в начальном состоянии, поэтому наш автомат принимает её. Если требуются только непустые строки, понадобится дополнительное различие между «ещё ничего не прочитано» и «прочитано хотя бы что-то с чётным числом единиц». Меняется условие задачи — меняется и достаточный набор состояний.
Какие истории можно объединить
После префиксов 11 и 1001 автомат находится в одинаковом состоянии Ч. Любое одинаковое продолжение повлияет на них одинаково, поэтому хранить различие между этими историями для нашей задачи бессмысленно. Напротив, префиксы 1 и 11 объединять нельзя: уже пустое продолжение даёт разные решения о приёме.
Не всякую задачу можно решить фиксированным числом состояний. Для проверки произвольно глубоко вложенных скобок требуется помнить неограниченную глубину; обычного конечного автомата для этого недостаточно. В небольшом прикладном автомате отдельно определяют поведение на символах вне алфавита: отклонение, ошибка ввода или заранее заданная обработка. Молчаливое игнорирование таких символов способно изменить принимаемый язык.
От чтения к действию
А теперь — вы
Частые вопросы
Начальное состояние обязательно принимающее?
Нет: это зависит от того, должна ли приниматься пустая строка. В нашем примере она содержит чётное нулевое число единиц, поэтому Ч принимающее.
Почему состояние не равно последнему символу?
Последнего символа недостаточно для чётности всех единиц. Строки 01 и 11 заканчиваются одинаково, но число единиц имеет разную чётность.
Углублённый разбор
Синхронизирующее слово стирает неизвестное состояние
Управляющее слово может привести автомат в одно известное состояние независимо от неизвестного начального. Задача синхронизации изучает действие слова сразу на всём множестве состояний. Кратчайшее решение ищется среди образов этого множества, а проверка существования допускает последовательное сжатие пар.
Перед началом: Полный детерминированный автомат; Поиск в ширину.
Неизвестное состояние заменяется множеством возможностей
Пусть переход δ(q,a) определён для каждого состояния и буквы. Если начальное состояние неизвестно и может быть любым из Q, после слова w возможны состояния δ(Q,w)={δ(q,w):q∈Q}. Синхронизирующим называют слово, для которого это множество одноэлементно. Принимающие состояния здесь не участвуют: нас интересует управление состоянием, а не принятие языка.
Поиск начинается с Q. Каждая буква переводит текущее непустое подмножество в его образ. BFS до первого одноэлементного множества находит кратчайшее сбрасывающее слово; предки и метки рёбер восстанавливают последовательность команд. Состояний поиска может быть экспоненциально много. Объединение одинаковых образов безопасно, потому что будущее действие любой команды определяется только текущим множеством, а не историей его получения.
Почему попарная сливаемость достаточна для существования
Необходимость проста: слово, сжимающее Q, сжимает каждую пару. Обратно, предположим, что любую пару состояний можно слить некоторым словом. Пока текущий образ содержит хотя бы два состояния, выберем такую пару и применим сливающее её слово ко всему образу. Детерминированная функция не увеличивает число элементов, а выбранная пара становится одним элементом, поэтому размер образа строго уменьшается.
После не более |Q|−1 таких этапов остаётся одно состояние. Для нахождения слов, сливающих пары, достаточно графа неупорядоченных пар с переходами к их образам; диагональ означает успех. Это даёт критерий существования. Однако последовательность локальных слияний не обязана давать глобально кратчайшее слово: экономия длины — отдельная задача, которую в маленьком примере решает BFS по всем подмножествам.
Полнота переходов является условием модели
Если переход не определён, нельзя просто выкинуть соответствующее возможное состояние и объявить оставшуюся ветвь синхронизацией. Для такого начального состояния команда вообще не выполнима. В этой главе автомат полный, поэтому любой образ непуст и каждая последовательность допустима при любом старте. Для частичных автоматов нужны иное определение допустимости и отдельная проверка; критерий выше нельзя переносить без этой оговорки.
Сброс тремя буквами
Условие. Состояния Q={0,1,2}; буква a задаёт цикл 0→1→2→0, буква b задаёт 0→0,1→1,2→1. Найдите кратчайшее синхронизирующее слово.
- Буква a переставляет Q и не уменьшает неопределённость. После b образ равен {0,1}.
- Применим a к {0,1}: получится {1,2}. Следующая b сливает оба состояния в1. Поэтому bab — сбрасывающее слово длины 3.
- Проверим все длины меньше 3. После ε и a остаётся Q, после b — {0,1}; после aa остаётся Q, после ab и bb — {0,1}, после ba — {1,2}. Ни один образ не одноэлементный.
- Прямые запуски bab из0,1,2 заканчиваются в1. Перебор меньших длин доказывает минимальность независимо от того, каким способом было найдено слово.
Ответ. Минимальная длина 3; один кратчайший сброс — bab, конечное состояние 1.
Проверка. Независимая таблица трёх запусков даёт 0→0→1→1, 1→1→2→1, 2→1→2→1. Все семь слов длин 0,1,2 оставляют не менее двух возможных состояний.
Где легко ошибиться. Не путайте склеивание неразличимых по языку состояний со слиянием состояний действием входного слова. Минимизация автомата и синхронизация отвечают на разные вопросы.
Проверьте понимание
Вопросы к этой главе
Обязательно ли сбрасывающее состояние финально?
Нет. У задачи управления может вообще не быть выделенного множества финалов. Требуется лишь одинаковый итог из всех возможных стартов. При необходимости попасть именно в заданное состояние это нужно добавить отдельным условием.
Почему нельзя ограничиться поиском самого короткого слова для одной пары?
Оно может не слить остальные состояния и после применения изменить удобство дальнейших слияний. Попарная сливаемость доказывает существование полного сброса, но длину общего решения следует оптимизировать по текущему образу всех состояний.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Sertaç Karahoda: Synchronizing Heuristic, §2–3
Прочитаны определения δ(S,w), reset word, mergeable pair и парного автомата. Используются критерий сжатия пар и собственный полный поиск по подмножествам; результаты GPU и экспериментальные ускорения не используются.
Автомат снизу вверх распознаёт свойство дерева
Конечный автомат может читать не только цепочку символов, но и дерево. Состояние поддерева передаёт наверх ровно ту информацию, которая нужна родителю. Построим двухсостоянийный автомат для нечётного числа отмеченных листьев и докажем его инвариант структурной индукцией.
Перед началом: Корневое дерево и рекурсивное поддерево; Чётность и исключающее ИЛИ.
Арность символа входит в формат входа
Возьмём ранжированный алфавит: a, b имеют арность 0 и обозначают листья; f имеет арность 2 и обозначает узел с двумя упорядоченными детьми. Корректные деревья строятся рекурсивно: a, b и f(t1, t2). Слово f(a) не является корректным входом этого алфавита, даже если можно угадать недостающего ребёнка.
Детерминированный автомат снизу вверх назначает состояние каждому листу, а в узле f вычисляет новое состояние по двум уже найденным состояниям детей. Дерево принимается, если состояние корня входит в заданное множество финальных. Начального состояния в смысле начала чтения строки здесь нет: вычисление начинается одновременно с листьев и объединяет сведения по форме дерева.
Два состояния хранят инвариант чётности
Пусть Q={0,1}, где состояние обозначает число листьев a по модулю 2. Зададим δ(a)=1, δ(b)=0, δ(f, p, q)=p⊕q; финально только 1. Для листа инвариант очевиден. Внутренний узел объединяет непересекающиеся наборы листьев детей, поэтому их количества складываются, а остатки по модулю 2 складываются через XOR.
Структурная индукция доказывает правильность на деревьях любой конечной высоты. Автомат не хранит точное число a и не ограничивает размер дерева двумя состояниями. Он хранит только достаточный для поставленного вопроса остаток. Из состояния 0 нельзя заключить, что листьев a нет: их может быть 2,4 или другое чётное число.
Проверка конкретного дерева и изменение одного листа
Рассмотрим t=f(f(a, b), f(a, a)). Левое поддерево имеет состояние 1⊕0=1, правое 1⊕1=0, корень 1⊕0=1. Дерево принимается, поскольку в нём три листа a. Если заменить последний лист a на b, правое состояние станет 1, а корень 0: новый вход отвергается с двумя отмеченными листьями.
Однократный обход обрабатывает каждый узел один раз; при постоянной таблице переходов требуется O(n) времени по числу узлов. Рекурсивная реализация использует стек высоты дерева, а не обязательно логарифмической глубины. Баланс дерева заранее не предполагается. Анализ относится к уже заданной корректной структуре; синтаксический разбор текстовой записи является отдельной стадией.
Три отмеченных листа и два состояния
Условие. Для δ(a)=1, δ(b)=0, δ(f, p, q)=p⊕q и финального состояния 1 вычислите результат на t=f(f(a, b), f(a, a)). Затем замените последний a на b.
- Листья исходного дерева получают состояния 1,0,1,1.
- Внутренние состояния равны δ(f,1,0)=1 иδ(f,1,1)=0.
- Корень получает δ(f,1,0)=1, поэтому t принимается. Прямой счёт даёт три листа a.
- После замены последнего a на b состояния детей корня равны 1 и 1, корень 0. Получены два листа a, поэтому изменённое дерево отвергается.
Ответ. Исходное дерево принимается с корневым состоянием 1; изменённое отвергается с состоянием 0.
Проверка. Независимый рекурсивный подсчёт числа листьев a даёт 3 и 2. В обоих случаях состояние автомата совпадает с остатком этого числа по модулю 2; тот же инвариант проверяется на всех малых деревьях.
Где легко ошибиться. Не считайте число состояний ограничением числа узлов входного дерева и не путайте чётный остаток с нулевым точным количеством.
Проверьте понимание
Вопросы к этой главе
Может ли автомат с двумя состояниями читать очень большое дерево?
Да. Два состояния ограничивают хранимое локальное резюме, а не число узлов. Один и тот же переход применяется во всех подходящих узлах.
Почему нельзя подать f(a) в приведённую таблицу?
Символ f имеет фиксированную арность 2. Такой вход нарушает формат дерева; это не обычный отрицательный результат распознавания корректного дерева.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Gécseg–Steinby: Tree Automata, §2.1–2.2
Ранжированные деревья и конечное распознавание от листьев к корню. Двухсостоянийная таблица, два дерева и индуктивный инвариант чётности разработаны для этой главы.
Алгоритм Бржозовского: два обращения вместо уточнения пар состояний
Два обращения слова возвращают его обратно, но для минимизации автомата этого наблюдения мало. Существенна промежуточная детерминизация: после неё второе обращение создаёт подмножества с различимыми будущими языками. Построим все состояния на небольшом неминимальном ДКА и докажем, почему последнее слияние уже не требуется.
Перед началом: Обращение автомата; Детерминизация множеством возможных состояний.
Четыре операции должны идти в правильном порядке
Конечный полный ДКА с известным стартом. После каждого обращения строятся только достижимые подмножества; пустое подмножество при необходимости сохраняется.
Обозначим обращение через R, а детерминизацию с удалением недостижимых подмножеств через D. Конструкция имеет вид D(R(D(R(A)))). В R меняются направления всех буквенных рёбер, прежние финалы становятся начальным множеством, прежний старт — финалом. В D один переход переводит целое текущее множество возможных состояний в следующее.
Первое обращение распознаёт Lᴿ, следующая детерминизация сохраняет этот язык. После второго обращения снова получается L, а последняя детерминизация даёт ДКА для L. Однако равенство языков само по себе доказывает только корректность распознавания. Минимальность следует из отдельного свойства последнего построения.
Достижимость старого состояния различает новые подмножества
Пусть B — достижимый ДКА со стартом b₀. Рассмотрим два разных состояния S,T детерминизированного обращения B. Выберем q, принадлежащее ровно одному из множеств. Так как B достижим, существует слово w, ведущее b₀ в q. В обращённом автомате чтение wᴿ из множества закончится с возможностью попасть в b₀ тогда и только тогда, когда q входило в исходное множество.
Причина последнего «тогда и только тогда» — детерминированность B: из b₀ по w достигается единственное q. Поэтому wᴿ различает S и T по приёму. Все разные достижимые подмножества попарно различимы, а значит полученный ДКА минимален. В нашем алгоритме роль B играет результат первой детерминизации, который достижим по самому способу построения.
Минимальность результата не ограничивает промежуточный рост
Подмножества нужно действительно строить по достижимым переходам. Простое перечисление всех 2ⁿ вариантов добавило бы недостижимые строки и не дало бы минимального представления из старта. Пустое подмножество — обычная отвергающая ловушка, если до него есть путь; удалять его из полного ДКА без изменения формата нельзя.
При больших входах промежуточное обращение может потребовать много подмножеств. Поэтому краткая формулировка алгоритма не означает малого расхода памяти. В отличие от уточнения разбиения здесь перестраивается представление языка. Для маленьких автоматов зато легко независимо проверить каждое новое подмножество и получить явные различающие продолжения.
Из трёх исходных состояний остаются два
Условие. У ДКА старт 0, финал только 1. Из любого состояния q∈{0,1,2} переход по a ведёт в 1, по b — в 2. Минимизируйте двойным обращением.
- Исходный язык состоит из непустых слов, заканчивающихся на a. Состояния 0 и 2 не принимают пустое продолжение и имеют одинаковые переходы, но пока записаны отдельно.
- Первое обращение начинается с {1}. Обозначим S={1},T={0,1,2},Z=∅. Получаем S:a→T,b→Z; T:a→T,b→T; Z:a→Z,b→Z. Принимает только T, содержащее старый старт 0.
- Второе обращение начинается с {T}, а его финалом становится S. При детерминизации достижимы U={T} и V={S,T}. По a из обоих идём в V, по b — в U.
- Состояние V принимает, поскольку содержит S; U не принимает. Получен двухсостоянийный ДКА того же условия окончания на a.
- U и V различаются уже пустым продолжением, оба достижимы. Значит два состояния необходимы; это отдельно подтверждает минимальность на данном примере.
Ответ. Минимальный ДКА имеет два состояния U,V; по a переходит в принимающее V, по b — в непринимающее U.
Проверка. Поиск в произведении исходной и конечной таблиц не находит слова с различными ответами. Промежуточный ДКА имел три достижимых подмножества; обещание минимальности относится к результату всей конструкции.
Где легко ошибиться. Не пропускайте детерминизацию между обращениями. Один разворот рёбер, выполненный дважды, вернёт старую неминимальную схему, а не доказанно минимальный ДКА.
Проверьте понимание
Вопросы к этой главе
Что получится, если исходный язык пуст?
Начальное множество первого обращения пусто. При детерминизации остаётся одна отвергающая ловушка; после всей конструкции минимальный полный ДКА пустого языка также имеет одно состояние.
Почему в доказательстве важна достижимость B?
Для состояния q из разности S и T требуется слово от b₀ до q. Без него предложенное различающее продолжение не построено. Первая детерминизация сохраняет только достижимые состояния и тем самым обеспечивает эту предпосылку.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Ganty, Gutiérrez and Valero: A Congruence-based Perspective on Automata Minimization Algorithms, Theorem 17
Сверены последовательность R–D–R–D и теорема минимальности. Собственный пример и доказательство различимости через достижимое q изложены отдельно; сравнение таблиц выполняется поиском в произведении.
Видимый стек отличает вложенные вызовы от обычного конечного состояния
Равное число открытий и закрытий не спасает слово ([)]: типы вложенности перепутаны. Видимый стек выбирает действие по виду входного символа, а в вершине хранит ожидаемый возврат. Сопоставим такой потоковый разбор с простым счётчиком и с автоматом, которому дерево уже дано готовым.
Перед началом: Конечный автомат; Стек и порядок последним вошёл — первым вышел.
Алфавит заранее сообщает действие над стеком
Детерминированный видимый стек для двух типов скобок и внутренних букв a,b,c. В нашей задаче принимаются только полностью согласованные слова с пустым стеком в конце.
Разделим символы на вызовы (, [, возвраты ), ] и внутренние a,b,c. Открывающая скобка кладёт в стек ожидаемый тип закрытия. Закрывающая обязана совпасть с вершиной и снять её; пустой стек или другой тип дают отказ. Внутренняя буква стек не меняет. Тип действия определяется символом, а не произвольным решением автомата.
Для этой проверки достаточно одного обычного управляющего состояния и отвергающего исхода; неограниченная память заключена в стеке, а не в числе состояний. В нашей модели успех дополнительно требует пустого стека после всего слова. Общий класс видимых магазинных автоматов допускает другие условия приёма, поэтому пустой стек здесь является частью конкретной задачи.
Инвариант хранит последовательность незавершённых вложений
После каждого допустимого префикса стек снизу вверх содержит ожидаемые закрытия всех ещё незавершённых вызовов от внешнего к внутреннему. Открытие добавляет самое внутреннее ожидание. Правильный возврат закрывает ровно его. Индукция по длине префикса показывает, что принятие с пустым стеком означает корректность всех пар и отсутствие незакрытого хвоста.
Один счётчик глубины этого не хранит. В слове ([)] глубины равны 1,2,1,0, нигде не отрицательны, но первый возврат ) встретил бы ожидаемую ]. Ошибка обнаруживается сразу на этом символе. Дополнительная проверка только итоговой глубины ноль не восстановит потерянную информацию о типах.
Готовое дерево и поток символов требуют разной памяти
Автомат снизу вверх на дереве получает структуру вложенности вместе со входом. При чтении обычной строки её ещё нужно восстановить. Стек выполняет именно эту работу. Для слова длины n проверяется каждый символ один раз; время линейно, память пропорциональна максимальной глубине, которая без дополнительного ограничения может достигать n.
Если заранее ограничить глубину D, все возможные стеки конечны и их можно включить в состояния ДКА. При двух типах до глубины D имеется Σⱼ₌₀ᴰ2ʲ допустимых стеков, плюс отказ. Для неограниченной глубины такого фиксированного конечного списка нет: разные префиксы из одних открывающих скобок различаются нужным количеством закрытий.
Два вложения и внутренние буквы
Условие. Проверьте (a[b]c) и ([)]. Показывайте ожидаемые закрытия в стеке, перечисляя их снизу вверх.
- Для первого слова после ( стек содержит ). Буква a сохраняет его; после [ стек равен )], поскольку следующей нужно закрыть квадратную скобку.
- Буква b ничего не меняет. Символ ] совпадает с вершиной, после него остаётся только ). Буква c снова не меняет стек.
- Последний ) снимает оставшееся ожидание. Конец ввода достигнут с пустым стеком; слово принимается. Глубины по символам равны 1,1,2,2,1,1,0.
- Во втором слове после ([ ожидается стек )]. На следующем символе ) вершина равна ], поэтому слово отвергается до попытки прочитать последний ].
- Независимо удалим внутренние буквы и последовательно сократим соседние правильные пары. У первого слова ([]) сокращается до (), затем до пустого. У ([)] ни одного подходящего соседнего сокращения нет.
Ответ. (a[b]c) принимается; ([)] отвергается на третьем символе из-за несовпадения типа.
Проверка. Стековый проход и независимое сокращение правильных соседних пар дают одинаковый результат на всех словах длины до шести над (,),[,],a. Проверка одной глубины на втором примере дала бы ошибочный успех.
Где легко ошибиться. Видимость действия не означает, что достаточно знать только глубину. При нескольких типах вызовов стек хранит последовательность типов, а конец слова с незакрытым ожиданием в данной задаче не принимается.
Проверьте понимание
Вопросы к этой главе
Почему внутренние буквы не требуют отдельной глубины?
Их класс заранее отделён от вызовов и возвратов. Они могут менять управляющее состояние в более сложном автомате, но по определению не добавляют и не снимают стековый символ. В нашем примере состояние также остаётся тем же.
Сколько стековых состояний нужно при двух типах и D=2?
Пустой стек, два одноэлементных и четыре двухэлементных дают семь допустимых вариантов. Полный конечный проверяющий автомат добавляет состояние отказа для переполнения, неправильного возврата и недопустимого символа.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Alur and Madhusudan: Visibly Pushdown Languages, introductory definition
Прочитано разделение алфавита на вызовы, возвраты и внутренние символы с синхронными стековыми действиями. Наше условие пустого стека и обе скобочные трассы заданы отдельно; другие условия приёма общего класса не исключаются.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как читать составное условие с И и ИЛИ
Как проверять составные условия с И и ИЛИ: логические значения частей, включающее «или», скобки и короткое вычисление в Python.
Открыть темуПочему поиск совпадения отличается от проверки всей строки
На коде из трёх цифр различаем поиск фрагмента и проверку целого поля, проверяем перевод строки и явно выбираем разрешённый алфавит.
Открыть тему