Информатика · объяснение и практика
Теорема Майхилла — Нероуда: конечные классы продолжений строят минимальный автомат
Доказать эквивалентность регулярности конечности классов правой конгруэнции и построить канонический минимальный ДКА по классам продолжений.

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
Два префикса различимы, если существует общее продолжение, после которого ровно одно из двух слов принадлежит языку. Такие префиксы не могут приводить ДКА в одно состояние. Набор из k попарно различимых префиксов требует как минимум k состояний.
Метод и постановка
Сначала задайте язык независимо от конкретного автомата. Затем найдите несколько префиксов, которые представляют разные будущие обязательства. Если автомат после двух префиксов оказался в одном состоянии, любое одинаковое продолжение обработается одинаково. Поэтому одно различающее продолжение для пары доказывает, что эти состояния должны быть разными.
Для набора префиксов проверяются все пары. Продолжение может быть своим для каждой пары; одно универсальное продолжение не требуется. Запишите таблицу свидетелей или общее правило их выбора. Это положительное доказательство нижней границы, которое не зависит от того, насколько удачно нарисован предполагаемый автомат.
Определите эквивалентность префиксов: x и y относятся к одному классу, если для любого суффикса z принадлежность xz и yz языку совпадает. Обратное направление теоремы тоже конструктивно. Если классов конечное число, сделайте их состояниями автомата, начальным назначьте класс пустого слова, переходом по букве a — класс xa из класса x. Переход корректно определён: эквивалентность x и y проверяет в том числе все продолжения az, значит xa и ya также эквивалентны. Принимающими служат классы слов языка; пустой суффикс гарантирует однозначность этого выбора. Так конечный индекс не только ограничивает размер, но и строит распознающий автомат.
Проверка и границы вывода
Нижняя граница сама по себе ещё не даёт автомат с таким числом состояний. Для точного минимума предъявите также построение нужного размера и проверьте переходы и принимающие состояния. Совпадение нижней и верхней границ завершает доказательство. Этот подход отличается от детерминизации НКА: конструкция подмножеств сохраняет язык, но часто создаёт больше состояний, чем необходимо.
Нельзя считать два состояния различными только из-за разных номеров, цветов на диаграмме или разных прочитанных слов. Различие должно проявляться в будущем принятии хотя бы одного общего продолжения. Также не ограничивайтесь проверкой только односимвольных суффиксов, если язык требует более длинного свидетеля. Пустое продолжение допустимо и часто сразу отделяет принимающий класс от непринимающего. Метод применим и к бесконечному семейству префиксов: бесконечно много попарно различимых классов исключает любой конечный ДКА.
Пример
Язык состоит из двоичных слов, число единиц в которых делится на три. Возьмём префиксы ε,1,11. Пустой суффикс отделяет ε от обоих остальных. Суффикс 1 отделяет 1 от 11: всего получается две и три единицы.
Нужно не меньше трёх состояний. Автомат, хранящий остаток числа единиц по модулю три, имеет ровно три состояния: ноль не меняет остаток, единица увеличивает его на один. Нижняя и верхняя границы совпали.
От чтения к действию
А теперь — вы
Частые вопросы
Нужен один суффикс для всех пар?
Нет. Для каждой пары достаточно собственного различающего продолжения.
Разные имена состояний доказывают минимальность?
Нет. Минимальность требует различимости будущего поведения, а не различий в обозначениях.
Углублённый разбор
Фактор автомата требует устойчивой эквивалентности
Произвольное разбиение состояний ДКА нельзя автоматически превратить в меньший автомат. Чтобы переход класса не зависел от выбранного представителя, эквивалентность должна сохраняться каждой буквой и уважать принимающий статус.
Перед началом: Эквивалентность состояний; Фактор множества.
Представитель класса не должен менять назначение
Пусть задано разбиение Q на классы отношения ~. Предполагаемый фактор имеет переход [q]→[δ(q,a)]. Он корректно определён только при условии: q~r влечёт δ(q,a)~δ(r,a) для каждой буквы a. Иначе один класс по одной букве имел бы два разных назначения в зависимости от представителя, что нарушает определение детерминированного перехода.
Кроме устойчивости переходов, каждый класс должен быть целиком принимающим или целиком непринимающим. Тогда можно определить финальные классы без неоднозначности. Эти два условия проверяются непосредственно по таблице и заданному разбиению. Не требуется заранее доказывать, что отношение является самой крупной эквивалентностью поведения или что полученный фактор минимален.
Гомоморфизм сохраняет состояние после любого слова
Пусть π переводит состояние в его класс. Условие устойчивости записывается π(δ(q,a))=δ̄(π(q),a). Индукция по длине слова продолжает это равенство на любой суффикс. Из согласованности финалов следует совпадение принятия исходным автоматом и фактором при соответствующих начальных состояниях. Это и есть доказательство сохранения языка.
Даже объединение действительно эквивалентных состояний может потребовать объединить ещё некоторые классы. Если их переходы пока лежат в разных классах, частично выполненное слияние не образует фактор. Можно расширять отношение до устойчивого замыкания, проверяя при каждом новом объединении отсутствие конфликта принимающих статусов. Простого утверждения «эти две вершины ведут себя одинаково» недостаточно для всей заданной таблицы классов.
Устойчивое разбиение не обязательно самое грубое
Разбиение на отдельные состояния всегда устойчиво и согласовано с финалами, но ничего не сокращает. Более грубый допустимый фактор может существовать. Поэтому проверка корректности предложенного сжатия и поиск минимального ДКА являются разными задачами. Первая проверяет локальные условия таблицы, вторая сравнивает будущие языки состояний и ищет максимально возможные слияния.
Практический валидатор для каждого класса и каждой буквы собирает множество классов назначений. Оно должно содержать ровно один элемент для полного ДКА. Отдельно проверяется однородность финального признака. Такие свидетельства объясняют причину отказа: конкретная пара представителей и буква полезнее абстрактного сообщения о неверной минимизации.
Частичное слияние чётных остатков
Условие. Однобуквенный ДКА имеет состояния 0,…,5, переход i→i+1 mod 6, старт 0 и финалы {0,2,4}. Сравните разбиение по чётности и разбиение {{0,2},{1},{3},{4},{5}}.
- В разбиении по чётности классы E={0,2,4} и O={1,3,5}. Каждый переход меняет класс, а все финалы находятся ровно в E.
- Фактор имеет два состояния и распознаёт слова чётной длины. Проекция остатка на его чётность согласуется с каждым переходом.
- Во втором разбиении представители 0 и 2 одного класса переходят в 1 и 3. Эти назначения лежат в разных классах, поэтому факторный переход не определён однозначно.
- Отказ не означает, что 0 и 2 различимы по будущему языку. Они эквивалентны, но предложенное частичное слияние ещё не закрыто относительно переходов.
Ответ. Разбиение по чётности корректно и даёт два состояния; частичное слияние некорректно.
Проверка. Проверка таблицы всех шести переходов подтверждает устойчивость чётности; пара 0,2 и буква a служат точным контрпримером для второго разбиения.
Где легко ошибиться. Корректность фактора относится ко всему разбиению. Одно допустимое по смыслу слияние может потребовать дальнейшего объединения классов назначений.
Проверьте понимание
Вопросы к этой главе
Можно слить финальное и нефинальное состояния?
Для фактора, сохраняющего язык из каждого состояния, нельзя: пустое продолжение уже различает их. Начальная недостижимость может позволить удалить вершины, но это другая операция.
Устойчивость надо проверять на всех словах?
Достаточно на отдельных буквах. Индукция переносит её на произвольное слово, если таблица переходов полна и условие проверено для каждой буквы алфавита.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Eric Blais: Myhill–Nerode theorem
Прочитано определение эквивалентности по всем продолжениям. Здесь проверяется иная практическая задача: допустимость заданного разбиения состояний как фактора, включая контрпример неустойчивого частичного слияния.
Обращение языка меняет направления переходов
Обращение языка читает каждое его слово в обратном порядке. Для автомата это разворот путей, обмен стартовых и принимающих ролей и обычно появление недетерминизма, даже если исходная схема была детерминированной.
Перед началом: Путь конечного автомата; Множество начальных состояний НКА.
Разворот пути задаёт конструкцию автомата
Для языка L положим Lᴿ={wᴿ:w∈L}. Возьмём ДКА и обратим каждое ребро, сохранив его буквенную метку. Все прежние финалы становятся начальными состояниями, а прежний старт — единственным финалом. Путь с метками a₁,…,a_n от старого старта к старому финалу превращается в путь с метками a_n,…,a₁ в новой схеме.
Если формат разрешает только один старт, добавьте новую вершину с ε-переходами во все старые финалы. Это технически эквивалентно множеству стартов. Если старый старт был финальным, пустое слово должно остаться принятым. Если старых финалов нет, новый язык пуст; нельзя назначать произвольную начальную вершину и случайно добавить слова.
Детерминированность не сохраняется при развороте
В исходном ДКА у состояния ровно одно исходящее ребро каждой буквы, но входящих рёбер той же буквы может быть несколько. После разворота они становятся альтернативными назначениями. Кроме того, прежних финалов может быть много. Следовательно, развёрнутая схема естественно является НКА, а не обязательно ДКА с тем же количеством состояний.
Если нужен ДКА для Lᴿ, его состояния строятся как достижимые подмножества развёрнутого НКА. Их может оказаться больше числа исходных состояний. Само сохранение регулярности не обещает сохранения минимального размера. Причина роста — необходимость помнить множество возможных предшественников, а не изменение входного алфавита или добавление новых букв.
Обращение отличается от дополнения
Дополнение полного ДКА меняет финальные признаки и оставляет направление чтения прежним. Обращение меняет порядок символов каждого слова и разворачивает рёбра. Для несимметричного языка эти операции дают совершенно разные множества. Например, условие на суффикс после обращения превращается в условие на префикс, а отрицание суффиксного условия имеет другой смысл.
Проверка конструкции запускает исходный автомат на w и новый на wᴿ. Пустое слово, несколько старых финалов и вершины с несколькими входящими рёбрами одной буквы особенно полезны для тестов. Общая эквивалентность следует из взаимно обратного преобразования путей; ограниченный перебор лишь независимо проверяет конкретную таблицу и обработку начального множества.
Из трёх состояний в четыре подмножества
Условие. ДКА имеет старт 0, финалы {1,2}; по a любое состояние идёт в 1, по b состояния 0,2 идут в 0, а 1 — в 2. Постройте обращённый автомат.
- У развёрнутого НКА начальное множество {1,2}, финал 0. По a из 1 можно идти в {0,1,2}; из остальных состояний a-переходов нет.
- По b из 0 доступны {0,2}, из 2 доступно {1}, а из 1 назначений нет. Из начального множества a ведёт во всё Q, b — в {1}.
- Достижимы четыре подмножества: {1,2}, {1}, Q и ∅. Из {1} буква a ведёт в Q, b — в ∅; Q и ∅ затем поглощающие.
- Только Q содержит финал 0. Новый язык равен aΣ*∪baΣ*: a и ba принимаются, b и bb отвергаются. Это обращение исходного условия окончания на a либо ab.
Ответ. Начальное множество {1,2}; после детерминизации достижимы четыре состояния.
Проверка. Перебор слов до длины семи проверяет Lᴿ(w)=L(wᴿ); четыре подмножества попарно различаются продолжениями среди ε,a,ba.
Где легко ошибиться. При обращении нескольких финалов все они становятся стартами. Выбор только одного потеряет часть слов, а развёрнутая схема обычно недетерминирована.
Проверьте понимание
Вопросы к этой главе
Можно обратить НКА тем же способом?
Да, если корректно поменять множества стартов и финалов и развернуть также ε-рёбра. Доказательство через обращение принимающих путей остаётся тем же.
Двойное обращение возвращает исходный язык?
Да: (wᴿ)ᴿ=w. Представление автомата после промежуточной детерминизации может отличаться, но распознаваемый язык после второго обращения совпадёт с исходным.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Illinois CS/ECE374: Reversal
Прочитан раздел обращения языка через разворот переходов и начальных/конечных состояний. Собственный трёхсостоянийный автомат и четыре достижимых подмножества построены отдельно.
Кратчайшее слово, различающее два полных ДКА
Два полных ДКА могут по-разному распознавать язык, даже если их размеры и отдельные переходы похожи. Поиск в произведении автоматов либо выдаёт кратчайшее различающее слово с двумя трассами, либо заканчивается конечным сертификатом эквивалентности.
Перед началом: Полный детерминированный автомат; Поиск в ширину.
Одна буква одновременно двигает пару состояний
Пусть два ДКА имеют общий конечный алфавит и полные переходы. Состоянием сравнения служит пара(p,q); по букве a она переходит в(δ₁(p,a),δ₂(q,a)). Начальная пара соответствует пустому слову. Если ровно одна компонента пары принимающая, прочитанное слово различает языки. Принимающий статус нужно сравнивать и до первого перехода: иначе потеряется возможный ε-свидетель.
Пара определяет всё будущее сравнение после данного префикса. Поэтому повторно обрабатывать её по более длинному пути не требуется. BFS посещает пары по неубыванию длины слова, а первый обнаруженный различающий статус даёт минимальную длину. Ссылки на предыдущую пару и букву восстанавливают слово; одинаковая длина нескольких свидетелей не нарушает минимальности.
Полное исчерпание отличается от долгого отсутствия ошибки
В произведении не больше n₁n₂ пар. Если все достижимые пары проверены и ни одна не различает принятие, языки равны. Доказательство использует замкнутость найденного множества по каждой букве: любой следующий префикс остаётся внутри него. Простая проверка первых нескольких слов без такой границы не даёт сертификата равенства.
Если различающее слово существует, кратчайшая его парная трасса не повторяет состояние: цикл можно удалить, сохранив конечную различающую пару. Поэтому длина свидетеля не больше n₁n₂−1. Это общий конечный предел, а не утверждение, что каждое число внутри него обязательно достигается. BFS не обязан строить все слова экспоненциального перебора, поскольку общие пары объединяются.
Соглашения ввода являются частью языка
Полнота означает ровно одно назначение для каждой буквы в каждой строке. Если исходный автомат частичный, его сначала дополняют отвергающим поглощающим состоянием. Лаборатория требует полные таблицы и один общий алфавит, а пустой набор финальных состояний разрешает. При эквивалентности она показывает достижимые пары; при различии — слово и обе трассы. Это проверка двух заданных языков, а не минимизация одного автомата по заранее выбранному разбиению.
Последняя a против нечётного числа a
Условие. Алфавит a,b; оба старта 0, финалы {1}. У A переходы:0→a1,b0 и1→a1,b0. У B:0→a1,b0 и1→a0,b1. Найдите кратчайшее различающее слово.
- Пустое слово оставляет пару(0,0), обе компоненты отвергают. Слова длины 1 дают по a пару(1,1), по b пару(0,0); различий пока нет.
- Из пары(1,1) чтение a приводит в(1,0). Первый автомат принимает, второй отвергает. Восстановленное слово равно aa.
- Обе парные трассы: A идёт0,1,1; B идёт0,1,0. Таким образом, одно и то же слово действительно даёт разные результаты.
- Все более короткие слова ε,a,b уже проверены и имеют одинаковый статус. Поэтому длина 2 минимальна, а не просто достаточна.
Ответ. Кратчайший свидетель aa, длина 2; A принимает, B отвергает.
Проверка. Независимый перебор слов длины 0 и 1 подтверждает минимальность, отдельный прогон aa подтверждает различие. Предел произведения 4 допускает длину не больше 3 и согласуется с найденным результатом.
Где легко ошибиться. Не проверяйте только непустые слова и не останавливайтесь после нескольких одинаковых ответов. Равенство языков удостоверяет исчерпание достижимого замкнутого произведения, а различие может возникнуть уже на ε.
Кратчайшее слово, различающее два ДКА
Общий алфавит: 1–3 разные строчные латинские буквы. В каждом автомате 1–8 состояний 0,…,n−1. Строка таблицы: номер состояния, затем назначения по буквам алфавита в указанном порядке. Таблицы полные. Пустой список финальных состояний разрешён; ε также может быть свидетелем.
Проверьте понимание
Вопросы к этой главе
Нужно ли предварительно минимизировать оба ДКА?
Нет. Произведение работает с исходными полными таблицами, включая недостижимые состояния. BFS сам не посещает недостижимые пары. Минимизация может сократить работу, но не является условием корректности.
Если есть несколько кратчайших слов, ответ неоднозначен?
Минимальная длина определена однозначно, само слово — не обязательно. Алгоритм может вернуть любой свидетель этой длины; фиксированный порядок букв делает выбор воспроизводимым. В нашей задаче вопрос проверяет найденное aa, а не уникальность всех возможных свидетелей.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Skut, Piskorski, Daciuk: Finite-State Machines
Прочитан раздел эквивалентности двух автоматов: парная трасса и удаление цикла дают различающее слово короче |Q||Q′|. Наша реализация находит кратчайший свидетель BFS по достижимому произведению; таблицы двух двухсостоянийных автоматов созданы отдельно.
Хопкрофт: меньшая половина управляет минимизацией ДКА
Хопкрофт строит минимальный ДКА последовательным разделением блоков состояний. Причина разделения — разные ответы на переход в уже известный блок. Очередь разделителей и правило меньшей половины позволяют не начинать попарное сравнение состояний заново после каждого уточнения.
Перед началом: Полный детерминированный конечный автомат; Эквивалентность состояний по всем продолжениям.
Обратный образ блока является разделителем
Сначала удалим состояния, недостижимые из начального. Они не влияют на распознаваемый язык, но увеличивают число классов таблицы без необходимости. Начальное разбиение достижимых состояний состоит из принимающих и непринимающих блоков; пустой блок не хранится. Эти два статуса уже различимы пустым продолжением.
Для выбранного блока S и буквы a вычислим X={q:δ(q,a)∈S}. Каждый текущий блок B, пересекающий и X, и его дополнение, заменяется на пересечение B∩X и разность B вне X. Состояния разных новых частей после буквы a попадают в различимые группы. При этом никакие действительно эквивалентные состояния не разделяются: у них совпадает поведение после каждой буквы и любого дальнейшего продолжения.
Меньшая половина управляет очередью, а не результатом
Разделение блока всегда сохраняет обе непустые части. Правило меньшей половины относится только к новым заданиям в очереди. Если старый блок уже был ожидающим разделителем для некоторой буквы, его заменяют обеими частями. Если не был, достаточно добавить меньшую часть: действие большей можно восстановить из уже обработанного старого блока и действия меньшей.
При индексированных списках предшественников состояние попадает в меньшие вновь добавленные блоки не более логарифмического числа раз: размер содержащего его блока каждый раз хотя бы вдвое уменьшается. Это объясняет эффективную реализацию алгоритма. Само хранение очереди без индекса предшественников не гарантирует такой оценки времени; полный повторный просмотр таблицы может быть дороже.
Устойчивое разбиение даёт автомат и свидетельства минимальности
После исчерпания очереди каждый блок однороден по принимающему статусу, а все представители по каждой букве переходят в один и тот же блок. Поэтому факторная таблица определена однозначно. Индукция по длине продолжения показывает равенство языков состояний внутри каждого блока.
Разделённые ранее состояния уже имеют различающее продолжение: к свидетелю между блоками назначения приписывается буква, вызвавшая разделение. Так все разные достижимые итоговые классы различимы и фактор минимален. Инструмент ниже принимает полную конечную таблицу, показывает удалённые недостижимые состояния, шаги разделения и фактор. Пустой список принимающих состояний разрешён; тогда все достижимые состояния эквивалентны.
Из восьми строк таблицы остаются четыре состояния языка
Условие. Алфавит a,b, старт 0, финальные состояния {2,3}. Строки переходов по a,b: 0:(1,4), 1:(2,5), 2:(2,3), 3:(2,3), 4:(2,5), 5:(5,5), 6:(6,7), 7:(6,7). Постройте минимальный достижимый фактор.
- Из 0 достижимы ровно 0,1,2,3,4,5. Состояния 6,7 удаляются. Начальные блоки равны F={2,3} и N={0,1,4,5}.
- Обратный образ F по букве a среди достижимых равен {1,2,3,4}. Он делит N на {1,4} и {0,5}; блок F остаётся целым.
- Обратный образ блока {1,4} содержит 0 по обеим буквам, но не содержит 5. Поэтому {0,5} разделяется на {0} и {5}. Итоговые классы: {0},{1,4},{2,3},{5}.
- Обозначим классы Q,M,F,Z соответственно. Переходы Q по обеим буквам ведут в M; из M буква a ведёт в F, b в Z; F и Z замкнуты по обеим буквам. Только F принимающий.
- F отличается от остальных пустым словом. M отличается от Q и Z продолжением a; Q отличается от Z продолжением aa. Все четыре класса достижимы и попарно различимы, поэтому дальнейшее слияние невозможно.
Ответ. Минимальный достижимый ДКА имеет 4 состояния и принимает слова длины не меньше двух, у которых вторая буква равна a.
Проверка. Независимый поиск в произведении для каждой пары состояний подтверждает ровно четыре класса будущего языка. Отдельная проверка произведения исходного и факторного автоматов не находит слова с разными ответами.
Где легко ошибиться. Не выбрасывайте большую часть разделённого блока. Обе части остаются в разбиении; меньшая половина лишь ограничивает повторную работу очереди.
Минимизация полного ДКА по Хопкрофту
Алфавит:1–4 разные строчные латинские буквы. До 12 состояний 0,…,n−1; старт 0. Строка: состояние и по одному назначению на каждую букву. Таблица полная. Финалы можно оставить пустыми. Недостижимые состояния удаляются до минимизации.
Проверьте понимание
Вопросы к этой главе
Почему состояния 6 и 7 не образуют пятое состояние ответа?
Они недостижимы из старта 0 и не могут встретиться при чтении слова. Минимизация распознаваемого из старта языка проводится на достижимой части.
Что произойдёт при пустом множестве финальных состояний?
Ни одно продолжение ниоткуда не принимается. Все достижимые состояния эквивалентны и дают один непринимающий класс; пустой список финалов является корректным входом инструмента.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- John Hopcroft: An n log n algorithm for minimizing states
Исходный технический отчёт STAN-CS-71-190: разбиения эквивалентных состояний, обратные переходы и выбор меньшего подмножества для повторной обработки.
Неоднозначность НКА: одно слово и два разных принимающих прогона
Недетерминированность ещё не означает неоднозначности: лишняя ветвь может всегда отвергаться. И наоборот, два успешных пути могут снова оказаться в одной вершине. Построим проверку, которая хранит не только текущую пару состояний, но и факт прежнего расхождения; затем восстановим кратчайшее слово с двумя принимающими прогонами.
Перед началом: Принимающий путь НКА; Синхронное произведение и поиск в ширину.
Сравниваются прогоны одного и того же слова
НКА без ε с одним стартом; переходы заданы отношением, без различаемых параллельных копий одного и того же ребра.
Прогон без ε делает ровно один переход на каждый входной символ. Поэтому два прогона одного слова можно читать синхронно. Неоднозначность означает существование хотя бы одного слова с двумя разными принимающими последовательностями состояний. Количество отвергающих путей не важно, а разные слова сравнивать друг с другом нельзя.
Если текущие состояния равны, это ещё не доказывает совпадения всей истории. Два пути могли раньше разойтись, затем слиться и совместно дойти до финала. Простая проверка пары различных конечных состояний потеряет именно такие случаи. Поэтому к паре нужен отдельный бит памяти.
Расхождение нельзя забывать после слияния
Состояние проверки имеет вид (p,q,d), где d=1 означает, что прогоны уже различались на некотором прочитанном префиксе. Старт (q₀,q₀,0). Для буквы a выбираем любые p′∈δ(p,a),q′∈δ(q,a) и переходим в (p′,q′,d∨[p′≠q′]). Новый бит никогда не сбрасывается обратно в ноль.
Цель поиска: p и q оба финальные, d=1. Путь к такой тройке предъявляет одно слово и две успешные истории. Обратно, синхронное чтение любых двух разных принимающих прогонов обязательно приведёт в цель. Значит достижимость эквивалентна неоднозначности в объявленной модели. Сохранённые предшественники поиска в ширину дают кратчайшее свидетельство.
Конечная проверка заменяет бесконечный перебор слов
При n состояниях потенциальных троек не больше 2n². Кратчайший путь к цели не повторяет одну и ту же тройку: повтор можно вырезать с сохранением оставшегося пути. Поэтому при наличии неоднозначности существует свидетельство длины не более 2n²−1. Это удобная грубая граница, а не обещание, что каждое слово такой длины нужно перечислять.
У ε-переходов разные прогоны могут иметь неодинаковое число шагов, поэтому данная синхронизация напрямую не применяется. Удаление ε с сохранением только языка также не обязано сохранять число путей. Если различаются параллельные копии переходов, бит нужно обновлять по их идентификаторам; наша модель отношений специально исключает эту дополнительную трактовку.
Два пути принимают aa и встречаются в одном финале
Условие. Задан старт 0, единственный финал 3. Переходы: 0 по a идёт в 1 или 2; из 1 и 2 по a идём в 3. Других переходов нет. Проверьте неоднозначность и найдите кратчайшее свидетельство.
- В начале проверка находится в (0,0,0). После первой a можно выбрать пару (1,2,1): пути уже различаются.
- После второй a оба компонента приходят в 3. Получаем (3,3,1), а не (3,3,0): слияние не стирает историю.
- Обе тройки координат финальны, бит равен единице. Слово aa имеет два принимающих прогона: 0→1→3 и 0→2→3.
- Пустое слово не принимается, а после одной a ни 1, ни 2 не финальны. Значит более короткого неоднозначного слова нет. Последующие a не имеют перехода из 3, поэтому других принимаемых длин также нет.
Ответ. НКА неоднозначен. Кратчайшее слово aa имеет ровно два принимающих прогона, хотя их финальная вершина одна.
Проверка. Прямой подсчёт путей по длинам 0,1,2,3 даёт числа принимающих прогонов 0,0,2,0. Независимый поиск троек достигает цели на расстоянии два.
Где легко ошибиться. Не сбрасывайте флаг различия при p=q. Текущая вершина и история прогона отвечают на разные вопросы.
Проверьте понимание
Вопросы к этой главе
Каждый НКА с ветвлением неоднозначен?
Нет. Ветви могут принимать непересекающиеся продолжения или одна может никогда не доходить до финала. Проверяется существование двух успешных прогонов именно одного полного слова.
Детерминизация решает эту задачу автоматически?
Она сохраняет принимаемый язык, но объединяет разные пути в подмножество и теряет их количество. ДКА однозначен по своему исполнению даже тогда, когда исходный НКА был неоднозначен.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- ENS: Unambiguous Finite Automata
Прочитано определение неоднозначности и прогона без ε в разделе1. Произведение с сохраняемым битом, граница и четырёхвершинный пример построены и проверены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Лемма о накачке: разбиение выбирает противник, а степень выбираете вы
Построить корректное доказательство нерегулярности языка по лемме о накачке, сохраняя порядок кванторов и охватывая все допустимые разбиения.
Открыть темуОдин шаг ДКА хранит сразу все возможные состояния НКА
Детерминизировать двоичный недетерминированный автомат с ε-переходами, строя только достижимые подмножества и проверяя принадлежность слова.
Открыть темуТеорема Райса относится к смыслу программы: синтаксический тест остаётся другой задачей
Распознать нетривиальное семантическое свойство вычислимой частичной функции и правильно применить неразрешимость, не распространяя её на свойства текста программы.
Открыть тему