Информатика · объяснение и практика
Один шаг ДКА хранит сразу все возможные состояния НКА
Детерминизировать двоичный недетерминированный автомат с ε-переходами, строя только достижимые подмножества и проверяя принадлежность слова.

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
Состояние детерминированного автомата — множество возможных состояний исходного НКА. Перед чтением и после каждого символа добавляют ε-замыкание. Подмножество принимающее, когда в нём существует хотя бы одно принимающее состояние НКА.
Метод и постановка
Вначале уточните алфавит. Здесь входные символы — ноль и единица, а метка два в таблице переходов обозначает ε, то есть движение без чтения символа. Это служебная метка таблицы, она не становится третьей буквой входного слова. Начальное состояние ДКА содержит начальное состояние НКА и все вершины, доступные из него одними ε-переходами.
Для очередной буквы сначала соберите назначения всех переходов с этой буквой из текущего множества. Затем снова замкните полученный набор по ε. Если выполнить замыкание только перед первым символом, позже можно потерять допустимые пути. Циклы из ε-переходов не требуют бесконечного обхода: вершины добавляются в множество лишь один раз, пока новых достижимых состояний больше нет.
Проверка и границы вывода
Обход достижимых множеств создаёт конечную таблицу ДКА. Полный набор всех подмножеств служит верхней границей, но многие из них могут никогда не появиться. Пустое множество, если оно достижимо, является обычным отвергающим состоянием и переходит в себя по любой букве. Его удаление без договорённости о неполной таблице нарушает определение полного ДКА.
Проверьте построение независимым пошаговым моделированием НКА на коротких словах, включая пустое слово. Принимается существующий успешный путь; требование успеха всех состояний множества заменило бы недетерминизм другой логикой. Построенный автомат эквивалентен исходному по языку, но не обязательно минимален по числу состояний. Минимизация требует отдельной проверки различимости состояний и не входит в процедуру подмножеств.
Пример
Пусть из 0 есть ε-переход в 1, состояние 1 повторяет нули и по единице переходит в принимающее 2, а 2 повторяет единицы. Для слова 0011 последовательность множеств начинается с {0,1}, затем дважды {1}, затем дважды {2}.
Слово принимается. Пустое слово отвергается, поскольку начальное замыкание не содержит 2. Для слова 10 после единицы окажемся в {2}, а по нулю перейдём в пустое множество.
От чтения к действию
А теперь — вы
Частые вопросы
Пустое множество можно не показывать?
Если оно достижимо, это обычное отвергающее состояние ДКА; оно сохраняется в таблице.
Множество принимающее лишь при принятии всеми вершинами?
Нет. НКА принимает при существовании хотя бы одного принимающего пути.
Углублённый разбор
Удаление эпсилон-переходов без детерминизации
Эпсилон-переходы можно удалить, оставив те же отдельные состояния НКА. Для этого короткий переход должен поглотить все бессловесные движения до и после буквы, а принимающий статус — учесть бессловесное завершение.
Перед началом: Эпсилон-замыкание; Принимающий путь НКА.
Новый переход объединяет три участка старого пути
Обозначим через E(q) множество состояний, достижимых из q только по ε, включая само q. Для буквы a определим δ′(q,a)=E(∪_{r∈E(q)}δ(r,a)), где замыкание множества означает объединение замыканий его элементов. Новый НКА имеет прежнее множество состояний Q и прежнее начальное q₀. Подмножества здесь служат значениями перехода, а не новыми состояниями ДКА.
Множество принимающих нужно заменить на F′={q:E(q)∩F≠∅}. Иначе можно потерять принятие пустого слова или ε-завершение после последней буквы. Каждый новый переход потребляет ровно одну букву; ε-переходов больше нет. Вычисленные замыкания могут увеличить число рёбер, хотя число состояний остаётся прежним.
Почему сохраняются все слова, включая пустое
Любой старый принимающий путь разбивается на участки ε* a ε* между прочитанными буквами. По определению каждый такой участок представлен новым переходом. Оставшийся ε-хвост учитывается в F′. Обратно, каждый новый переход имеет свидетельствующий старый участок, и их можно склеить в старый путь с тем же словом. Для пустого слова переходов нет: условие принятия проверяет E(q₀)∩F.
Циклы из ε не требуют бесконечных списков путей. Замыкание является конечным множеством достижимых вершин и вычисляется обходом с отметками посещения. Но нельзя заменить его одним непосредственным ε-шагом: цепочка длины два или больше может открыть буквенный переход, которого иначе не видно. Именно достижимость, а не локальная соседность, входит в конструкцию.
Удаление ε и детерминизация решают разные задачи
После преобразования одна буква по-прежнему может вести в несколько состояний. Полученный автомат остаётся НКА. Если нужен ДКА, конструкция подмножеств выполняется уже отдельно. Поэтому сохранение числа состояний не противоречит возможному экспоненциальному числу состояний после детерминизации: это разные промежуточные представления одного языка.
Независимая проверка малой схемы запускает исходный ε-НКА по конфигурациям и сравнивает с новым автоматом без ε. В набор тестов включите пустое слово, слово с ε-шагом перед первой буквой и слово с ε-шагом после последней. Совпадение на конечном наборе ловит ошибки реализации; общее равенство языков следует из преобразования путей в обе стороны.
Сохранить четыре состояния
Условие. Исходный НКА имеет старт 0, финал 3 и рёбра 0→ε1,1→a1,1→b2,2→ε3,3→a3. Удалите ε без детерминизации.
- Замыкания равны E(0)={0,1},E(1)={1},E(2)={2,3},E(3)={3}. Поэтому новое множество финалов равно {2,3}.
- Из состояний 0 и 1 по a получаем {1}, а по b — {2,3}. Из 2 и 3 по a получаем {3}; остальные буквенные переходы пусты.
- Слово b теперь проходит из 0 сразу в принимающее множество {2,3}. Оно принималось и раньше благодаря ε-шагу после b.
- Оба автомата распознают a*ba*. Пустое слово и bb отвергаются, baa принимается. Во всех случаях число отдельных состояний остаётся четыре.
Ответ. Новый НКА имеет Q={0,1,2,3}, старт 0 и финалы {2,3}, без ε-рёбер.
Проверка. Перебор всех двоичных по алфавиту {a,b} слов длины до семи сравнивает два исполнения с предикатом: ровно одна b.
Где легко ошибиться. Удаление ε требует изменить не только буквенные рёбра, но и множество финалов. Иначе короткие слова с бессловесным завершением потеряются.
Проверьте понимание
Вопросы к этой главе
Нужно менять начальное состояние?
В данной конструкции нет: ε-движения перед первой буквой включены в δ′, а принятие пустого слова — в F′. Другие эквивалентные конструкции могут использовать множество стартов.
Число рёбер обязательно уменьшается?
Нет. Одна ε-цепочка может открыть много буквенных назначений. Состояний остаётся столько же, но плотность переходов способна вырасти.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Alfred Aho: ε-NFA and epsilon-closures
Прочитаны семантика ε-пути и определение ECLOSE. Сохранение исходных состояний при удалении ε, изменение принимающих состояний и собственный четырёхвершинный пример доказаны отдельно; детерминизация основного текста не повторяется.
Синхронное произведение НКА для пересечения языков
Пересечение языков НКА можно построить напрямую, синхронизируя два принимающих пути по каждой входной букве. Детерминизировать оба автомата заранее не требуется, но эпсилон-шаги нуждаются в отдельной обработке.
Перед началом: Недетерминированный переход; Декартово произведение.
Пара состояний хранит два параллельных исполнения
Рассмотрим НКА без ε над одним алфавитом. Состояния произведения — пары (p,q), старт — пара стартов, финалы — F₁×F₂. По букве a из (p,q) разрешены все пары (p′,q′), где p′∈δ₁(p,a), q′∈δ₂(q,a). Если хотя бы один набор назначений пуст, переходов по этой букве из данной пары нет.
Количество потенциальных состояний не превосходит |Q₁||Q₂|, хотя число переходов зависит и от ветвления. Существование пути в произведении означает одновременное существование двух путей на одном слове. Выбор недетерминированной ветви в первом автомате не ограничивает выбор во втором: декартово произведение сохраняет все их сочетания.
Свидетельства принятия должны совпасть по прочитанному слову
Если слово принадлежит обоим языкам, выберите по одному принимающему пути для каждого автомата. Они имеют одинаковое число буквенных шагов, поэтому их можно соединить попарно. Получится принимающий путь произведения. Обратно, проекции любого пути произведения являются путями исходных автоматов; финальная пара подтверждает принятие обоими.
Для ε-НКА буквенные шаги уже не обязаны занимать одинаковое число переходов. Нельзя просто потребовать одновременного ε-шага в обоих компонентах: один из них может двигаться бессловесно, пока второй остаётся на месте. Безопасный путь — сначала удалить ε с сохранением языка, затем использовать описанное синхронное произведение. Это сохраняет конечность и даёт простой инвариант доказательства.
Пересечение нельзя заменить пересечением наборов имён
Номера состояний двух автоматов не имеют общего семантического смысла. Состояние p первого и q второго должно сохраняться как упорядоченная пара. Также нельзя объявить пару принимающей по условию «хотя бы один финал»: тогда получится другое языковое условие. Для пересечения нужны оба принимающих состояния на конце одного общего слова.
При проверке полезно сравнить продукт с независимыми запусками обоих автоматов и конъюнкцией их ответов. Отдельные отрицательные примеры должны удовлетворять только первому и только второму языку. Иначе неверное условие финальности может остаться незамеченным: на словах, принимаемых обоими или отвергаемых обоими, ошибки AND и OR часто не видны.
Подстрока и чётность
Условие. Первый НКА распознаёт наличие ab: из 0 по a идут 0 и 1, по b — 0; из 1 по b — 2; из 2 обе буквы оставляют 2, финал 2. Второй автомат хранит чётность числа a, старт и финал 0. Проверьте aab.
- Начальная пара равна (0,0). После первой a доступны (0,1),(1,1), поскольку первый автомат сохраняет и поиск, и начало предполагаемой подстроки.
- После второй a доступны (0,0),(1,0). Ветка в состоянии 1 от предыдущей буквы не продолжается по a, но новая ветка снова создаётся из 0.
- После b получаем (0,0),(2,0). Вторая пара принимающая, так как подстрока ab найдена и число a чётно.
- Слово ab удовлетворяет только первому условию, а baa — только второму. Оба отвергаются пересечением, в отличие от aab.
Ответ. aab принимается; ab и baa отвергаются.
Проверка. Полный перебор слов до длины семи сравнивает произведение с прямой проверкой подстроки ab и чётности количества a.
Где легко ошибиться. Синхронизация относится к буквам входа. Для ε-шагов нельзя требовать обязательного одновременного движения обоих компонентов.
Проверьте понимание
Вопросы к этой главе
Нужно удалить недостижимые пары?
Для корректности языка не нужно, но это уменьшает представление. Обход от стартовой пары строит только те состояния, которые действительно возникают на каком-либо слове.
Произведение обязательно детерминировано?
Нет. Если один компонент имеет несколько назначений, произведение обычно наследует несколько пар назначений. Детерминированность здесь не является условием доказательства пересечения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Illinois CS/ECE374: Language Transformations
Прочитаны преобразование автоматов и произведение для операций над языками. Синхронное произведение двух НКА без ε обосновано через пары путей; собственный пример содержит реальное ветвление, а не только ДКА.
Включение языков НКА требует учитывать все ветви второго автомата
Включение языков НКА имеет разные кванторы с двух сторон. Контрпримеру достаточно одной принимающей ветви первого автомата, но второй обязан отвергнуть его по всем ветвям. Поэтому обычная пара отдельных состояний не заменяет пару состояния и полного множества возможностей второго автомата.
Перед началом: Семантика НКА; Поиск в ширину.
Отрицание принятия нельзя получить одной неудачной ветвью
Требуется проверить L(A)⊆L(B). Нарушение — слово w, для которого существует принимающий прогон A и не существует принимающего прогона B. Если выбрать одну отвергающую ветвь B, это ещё не доказывает отказ слова: другая ветвь может закончиться в финале. Это принципиальное отличие от пересечения двух НКА, где достаточно найти по одной принимающей ветви с обеих сторон.
Рассматриваем НКА без ε-переходов над общим алфавитом; при их наличии сначала нужно корректно включить ε-замыкания. Состояние поиска имеет вид(p,S), где p — выбранная ветвь A после прочитанного слова, а S — все состояния B, достижимые этим словом. Для каждой буквы c и каждого p′∈δ_A(p,c) переходим в(p′,∪_{q∈S}δ_B(q,c)). Пустое S допустимо и означает, что у B больше нет ни одной продолжающейся ветви.
Плохая пара даёт проверяемый контрпример
Пара является свидетельствующей, если p финально в A и S не пересекается с финалами B. Тогда сохранённое слово действительно принимается A и отвергается B. Проверяем начальные пары тоже: пустое слово может нарушать включение. BFS по достижимым парам находит кратчайший контрпример; ссылки на предка и букву восстанавливают его без хранения всех слов.
Если всё достижимое пространство исчерпано без плохой пары, включение выполнено. Конечность следует из границы |Q_A|·2^|Q_B|, а не из произвольного ограничения длины тестовых слов. Цена может быть экспоненциальной из-за правой стороны: отсутствие принятых ветвей требует совместного отслеживания всех возможностей. Включение в обратную сторону является отдельным запуском, а эквивалентность требует обоих направлений.
Проверяйте смысл множества независимо от обхода
Для каждого шага полезно сопоставить S с прямым запуском НКА на префиксе. Единственная финальная вершина в S уже отменяет отрицательный вывод о B, сколько бы отвергающих ветвей рядом ни было. Для маленького примера полный перебор коротких слов подтверждает минимальность свидетеля, а инвариант множества объясняет правильность для всех длин. Это разделяет алгоритмическую проверку включения и случайную проверку нескольких примеров.
Одна отвергающая ветвь ещё не контрпример
Условие. A имеет единственное стартовое финальное состояние p с петлёй a, переходов по b нет. У B старт 0 финален, из0 по a идут 1 и2, финалы{0,1}; других переходов нет. Найдите кратчайшее слово L(A)\L(B).
- Начальная пара(p,{0}) не плохая: оба автомата принимают ε. После a получаем(p,{1,2}).
- Состояние 2 не финально, но1 финально. Следовательно a принимается B; выбор лишь ветви 0→2 дал бы ложный контрпример.
- После ещё одной a множество B пусто, так как ни1, ни2 не имеют выходов. Пара(p,∅) плохая, и слово aa действительно лежит в разности.
- Более короткие ε,a уже проверены. Слово b не принимается A и не может быть контрпримером. Значит aa имеет минимальную длину 2.
Ответ. Кратчайший контрпример aa; слово a не является контрпримером из-за принимающей ветви B.
Проверка. Прямые описания языков: L(A)=a*, L(B)={ε,a}. Их разность состоит из aⁿ при n≥2. Независимый запуск подмножеств подтверждает{0}→{1,2}→∅.
Где легко ошибиться. Не дополняйте НКА простой перестановкой финальных состояний. Это меняет условие «существует принимающая ветвь» на неверное условие вместо нужного «все ветви отвергают».
Проверьте понимание
Вопросы к этой главе
Зачем хранить A одним состоянием, а не множеством?
Контрпримеру достаточно одной принимающей ветви A; поиск сам недетерминированно разветвляется по её переходам. Для B необходимо доказать отсутствие всех принимающих ветвей, поэтому там требуется полное множество.
Пустое множество B означает ошибку построения?
Нет. Оно является нормальным достижимым состоянием детерминизации и остаётся пустым после любой следующей буквы. Если A в это время принимает, получен корректный контрпример включению.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Tomáš Vojnar: Antichain-based Inclusion Checking, word-automata section
Прочитаны classical inclusion и macro-state(r,P): одна ветвь A плюс все состояния B, принятие контрпримера при отсутствии финала B. Antichain-ускорения не применяются. Собственный пример a* против{ε,a} проверяет именно квантор всех ветвей.
Позиционный автомат Глушкова строится без эпсилон-переходов
Позиционный автомат Глушкова создаёт состояние для каждого вхождения буквы в регулярном выражении. Множества first, last и follow сразу задают переходы без ε-рёбер. Одинаковые буквы в разных позициях остаются разными состояниями, поэтому автомат может быть недетерминированным.
Перед началом: Регулярное выражение; Позиция символа.
Нумеруются вхождения, а не виды букв
Пометим каждую буквенную позицию выражения уникальным номером. First содержит позиции, способные быть первыми в непустом слове выражения, last — последними, follow(i) — позиции, которые могут непосредственно следовать за i. Отдельный признак nullable показывает принадлежность пустого слова. Одинаковая a в двух местах имеет разные номера, даже если после снятия меток входной символ один.
При объединении first и last объединяются. При конкатенации добавляется first правой части, если левая nullable, и симметрично last левой, если правая nullable; между каждой позицией last слева и first справа добавляется follow-связь. Для звезды сохраняются крайние множества и добавляются возвраты last→first, а nullable становится истинным. Эти правила вычисляются по синтаксическому дереву выражения.
Начальный узел и принимающие позиции определяют НКА
Добавим новое начальное состояние 0. Из него по букве c переходят в позиции first, помеченные c. Из позиции i по c переходят в позиции follow(i), помеченные c. Финальны позиции last; начальный 0 тоже финален ровно при nullable. Так каждый переход потребляет одну настоящую букву, и ε-рёбер нет, хотя само выражение может принимать ε.
Путь автомата перечисляет допустимые соседние позиции одного размеченного слова; снятие номеров даёт слово исходного выражения. Обратно, любой разбор слова по выражению определяет такую позиционную трассу. Это объясняет эквивалентность языка. Число состояний равно числу буквенных вхождений плюс 1, но follow-связей может быть квадратично много. Отсутствие ε не означает автоматически меньший размер таблицы переходов.
Несколько одинаково помеченных продолжений сохраняются вместе
Недетерминизм возникает, когда одна буква может означать продолжение звезды или начало следующей части. Выбирать одну ветвь по догадке нельзя. При исполнении хранится множество активных позиций; детерминизация при необходимости выполняется отдельно. Это отличается от производных выражений: там состояния являются остаточными языками, здесь — буквенными позициями синтаксиса. Оба способа могут распознавать один язык, имея разные промежуточные объекты.
Ветка звезды и завершающая b
Условие. Постройте позиционный НКА для r=(a|ba)*b. Нумеруйте a₁,b₂,a₃ внутри звезды и завершающую b₄. Проверьте bab и bb.
- Звезда nullable, поэтому first={1,2,4}; last={4}, всё r не nullable. Следования: follow(1)={1,2,4}, follow(2)={3}, follow(3)={1,2,4}, follow(4)=∅.
- Из0 по b доступны 2 и4. Это два смысла одной буквы: начало блока ba или уже финальная b. Узел 4 финален, но ветвь может закончиться только вместе со всем словом.
- Для bab после a остаётся{3}, после последней b получаем{2,4}. Наличие 4 означает принятие; первые ba составили один блок звезды.
- Для bb после первой b имеем{2,4}, а по второй b обе ветви исчезают:2 ждёт a,4 не имеет переходов. Следовательно bb отвергается.
Ответ. НКА имеет 5 состояний без ε-рёбер; bab принимается, bb отвергается.
Проверка. Независимый разбор на ноль или больше блоков a/ba с одной завершающей b подтверждает результаты. Перебор всех коротких слов сравнивает этот разбор с множествами активных позиций автомата.
Где легко ошибиться. Не объединяйте разные вхождения одной буквы в одно состояние до анализа языка. Позиционные номера сохраняют различие контекстов, а наличие финальной ветви на префиксе не разрешает проигнорировать остаток слова.
Проверьте понимание
Вопросы к этой главе
Как автомат принимает ε без ε-переходов?
Начальное состояние просто помечается финальным при nullable выражении. Переход не нужен, потому что не потребляется ни одной буквы. В нашей задаче r не nullable, поэтому 0 не финален.
Почему b само по себе принимается?
Звезда может породить пустое слово, после чего остаётся завершающая b₄. Переход 0→4 читает ровно эту букву. Это не означает принятия bb, для которого второго продолжения нет.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Allauzen, Mohri: A Unified Construction…, §3/Table2
Прочитаны маркированные позиции, null/first/last/follow и определение Glushkov automaton. Используется невзвешенный булев случай; semiring-обобщения не переносятся. Собственное выражение(a|ba)*b отличается от примеров статьи и прежней главы производных.
Уравнение языков и лемма Ардена
Лемма Ардена решает уравнения, в которых неизвестной является целый язык. Она различает наименьшее решение и единственное решение, а также сохраняет порядок конкатенации. Это позволяет исключать неизвестные языки из системы без перебора всех принимаемых слов.
Перед началом: Операции над языками; Звезда Клини.
Языки складываются объединением, но не числовым вычитанием
Рассмотрим X=AX∪B, где A,B известны, произведение означает конкатенацию языков. Язык A*B всегда является решением, поскольку A* содержит ε и все положительные степени A. Любое другое решение обязано содержать B, затем AB, A²B и все следующие степени. Следовательно A*B — наименьшее решение относительно включения независимо от того, входит ли ε в A.
Нельзя переносить AX в другую часть и делить на «1−A»: у объединения нет операции вычитания, обратной в нужном смысле. Корректное рассуждение опирается на развёртывание уравнения и включения. Если неизвестный язык стоит справа, именно A*B сохраняет порядок факторов. Для уравнения X=XA∪B аналогичная формула имеет вид BA*, потому что конкатенация обычно некоммутативна.
Отсутствие пустого слова обеспечивает единственность
Пусть ε∉A. Возьмём слово w любого решения X. Если оно не взято из B, уравнение заставляет представить его как uv, где u∈A, v∈X. Слово u непусто, поэтому длина v строго меньше длины w. Повторение не может продолжаться бесконечно: в конце получается слово из B. Значит w принадлежит некоторому AⁿB, и других слов сверх A*B в решении нет.
Если ε принадлежит A, убывание длины перестаёт работать. Например X={ε}X∪{a} означает лишь, что X содержит a: подходят {a} и {a,b}. Наименьшее решение по-прежнему есть, но единственность уже не гарантирована. Условие ε∉A является достаточным, а не утверждением, что при ε∈A каждое возможное уравнение непременно имеет несколько решений.
Исключение неизвестного проверяется подстановкой в обе строки
В системе языковых уравнений подставляем одну строку в другую, собираем известные коэффициенты и применяем лемму только после проверки её условий. Затем восстанавливаем исключённый язык. Проверка должна возвращаться ко всей системе: правильная первая строка сама по себе не удостоверяет вторую. Короткие слова полезны для обнаружения перепутанного порядка, но доказательство единственности даёт именно убывание длины.
Два взаимно рекурсивных языка
Условие. Решите систему X=aY∪{b}, Y=bX∪{ε} над алфавитом {a,b}. Здесь отдельные буквы обозначают одноэлементные языки.
- Подставим вторую строку в первую: X=a(bX∪{ε})∪{b}=abX∪{a,b}. Коэффициент {ab} не содержит ε.
- По лемме Ардена единственное решение первой строки X=(ab)*(a|b). Затем Y=b(ab)*(a|b)∪{ε}.
- Проверим X: aY∪{b}=ab(ab)*(a|b)∪{a,b}. Объединение нулевой степени и положительных степеней ab в точности равно (ab)*(a|b). Вторая строка выполнена по определению Y.
- Слово abb принадлежит X как один блок ab и завершающая b. Перестановка факторов в (a|b)(ab)* это слово теряет: после первого a остаётся bb, которое не является степенью ab.
Ответ. X=(ab)*(a|b), Y=b(ab)*(a|b)∪{ε}; пара языков единственна.
Проверка. Независимые последовательные приближения из пустых языков дают все слова этих выражений до заданной длины. Слова a,b,aba,abb появляются в X, а ε и ab не появляются. Подстановка доказывает равенство для всех длин.
Где легко ошибиться. Не заменяйте наименьшее решение единственным без проверки ε∉A и не переставляйте коэффициенты как числа. Обе ошибки могут сохранять несколько коротких примеров и менять весь язык.
Проверьте понимание
Вопросы к этой главе
Почему решение системы тоже единственно?
Любая её пара решений после подстановки обязана иметь X, решающий X=abX∪{a,b}; он единственен. Тогда вторая строка однозначно задаёт Y. Подстановка найденной пары доказывает существование, а это рассуждение — отсутствие других пар.
Нужно ли останавливать развёртывание после фиксированного числа шагов?
Для доказательства нет. Каждое отдельное слово имеет конечную длину, и непустые коэффициенты заставляют её убывать. Конечное вычисление приближений используется лишь как независимая проверка выбранных коротких слов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Klaus Sutner: Algebra of Regular Languages, Arden’s Lemma
Прочитаны уравнение X=AX+B, наименьшее решение A*B, условие ε∉A и доказательство единственности через длину слова. Собственная система двух языков и контрпример при ε∈A построены отдельно от примеров лекции.
Симуляция НКА безопасно убирает избыточные ветви
В наборе активных состояний НКА одна ветвь может полностью покрываться другой. Направленная симуляция даёт достаточный сертификат такого покрытия. Проверим, какую ветвь можно убрать, почему обратное удаление неверно и почему одностороннюю симуляцию нельзя объявлять равенством состояний.
Перед началом: Недетерминированный автомат без ε-переходов; Язык продолжений из состояния.
Покрывается каждое возможное продолжение
Для состояния p обозначим L(p) язык слов, после чтения которых из p можно попасть в финальное состояние. В активном множестве S распознаётся объединение L(p) по p∈S. Если L(p)⊆L(q) и оба состояния уже входят в S, удаление p не меняет этот объединённый язык. Нужно именно наличие другой покрывающей ветви, а не произвольная замена p новым более сильным состоянием.
Отношение R является прямой симуляцией, если для каждой пары(p, q)∈R выполнены два условия. Финальность p требует финальности q. Для каждого перехода p по букве a в p′ существует переход q по той же букве в q′ с(p′, q′)∈R. Квантор «для каждого — существует» следует направлению покрытия; перестановка кванторов проверяла бы другое свойство.
Почему из локальных условий следует включение языков
Доказательство проводится по длине принятого слова. Для пустого слова достаточно условия финальности. Если p принимает aw, выберем его первый переход по a. Симуляция даёт ответный переход q по a в состояние, снова связанное с оставшейся ветвью p. Индукция переносит принятие хвоста w. Поэтому любое слово из L(p) входит ив L(q).
Для конечного автомата кандидатное отношение можно проверять по конечным таблицам финальности и переходов. При поиске наибольшей симуляции сначала допускают все пары, совместимые по финальности, затем удаляют пары без нужного ответного перехода до стабилизации. Проверка является достаточной для включения языков; отсутствие симуляции в общем НКА само по себе не доказывает различия языков.
Удалить слабую ветвь, сохранив сильную
Пусть p по a переходит в финальное f; q по a ипо b тоже переходит в f. Других переходов нет, p, q нефинальны. Тогда L(p)={a}, L(q)={a, b}; отношение с(p, q), (f, f) и рефлексивными парами удовлетворяет симуляции. Из начального множества{p, q} можно убрать p, поскольку q уже принимает всё, что могла ветвь p.
Убрать q и оставить p нельзя: слово b потеряется. Также нельзя только на основании(p, q) слить состояния как эквивалентные. Для произвольных структурных изменений нужно отдельное доказательство сохранения языка. Пример рассматривает удаление избыточной ветви одного множества состояний, поэтому его обоснование прямо следует из включения и объединения языков.
Вторая ветвь принимает дополнительное слово
Условие. НКА имеет p−a→f, q−a→f, q−b→f; только f финально. Начальное множество{p, q}. Проверьте симуляцию p состоянием q и выберите допустимое удаление.
- Финальность согласована: p, q нефинальны, а f симулирует себя.
- Единственный переход p по a имеет ответный переход q по a в то же f. Поэтому p симулируется q.
- Языки продолжений равны L(p)={a}, L(q)={a, b}. Их объединение совпадает с L(q).
- Удаление p из начального множества сохраняет язык{a, b}. Удаление q оставило бы{a} и потеряло b.
Ответ. Можно убрать слабую ветвь p. Направление симуляции не позволяет вместо неё удалить q.
Проверка. Пустое слово не принимается, односимвольные a, b принимаются исходным набором и только q, а слова длины≥2 не принимаются ни одним из них. Это напрямую проверяет полное множество продолжений примера.
Где легко ошибиться. Не превращайте одностороннее включение языков в эквивалентность и произвольное слияние состояний.
Проверьте понимание
Вопросы к этой главе
Почему для перехода нужен ответ по той же букве?
Сравниваются языки одних и тех же входных слов. Ответ другой буквой изменил бы наблюдаемую строку, а потом не доказывал бы включения языков.
Что означает неудача поиска симуляции?
Только отсутствие данного локального сертификата. Более общий анализ языков может всё же установить включение; симуляция не заявлена полным решателем этой задачи.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Clemente–Mayr2019: simulation and NFA reduction, §3–4
Направленные отношения симуляции иих применение кконечным автоматам. Пример с тремя состояниями ииндуктивное доказательство для удаления одной покрываемой ветви приведены отдельно.
Линейное временное until проверяется по произведению с автоматом
Цель может быть доступна из каждого состояния, но всё же никогда не наступить на допустимом исполнении. Для сильного until это нарушение. Разберём маленький монитор обязательства и найдём контрпример вида «префикс плюс повторяемый цикл», который обычный поиск пути до цели пропускает.
Перед началом: Детерминизация и произведение состояний; Бесконечный путь и достижимость цикла.
Сильное until содержит два обязательства
Конечная тотальная система переходов, все бесконечные пути учитываются; справедливость выбора выходов дополнительно не предполагается.
На пути s₀,s₁,… формула p U q истинна, когда существует конечный номер j≥0 с истинным q в sⱼ, а p истинно во всех sᵢ при i<j. В самом sⱼ условие p уже не требуется. Если q истинно сразу, разрешён j=0: проверять p до начала пути не нужно.
Нарушения бывают двух видов. Либо до первого q встречается состояние без p, либо q не наступает вообще, хотя p может бесконечно оставаться истинным. Второй случай отличает сильное until от слабого. При проверке системы формула должна выполняться на каждом её пути; одной удачной ветви до q недостаточно.
Монитор помнит незакрытое обязательство
Добавим к состоянию системы режим «ждём», «успех» или «ошибка». Пока ждём, сначала проверяем q: оно переводит в успех. Если q ложно и p тоже ложно, переходим в ошибку; иначе продолжаем ждать. Успех и ошибка сохраняются при любых дальнейших наблюдениях. Порядок проверок существенен для состояния, где q истинно, а p ложно.
Достижимая ошибка сразу даёт конечный плохой префикс. Но отсутствие ошибки ещё не доказывает сильное until: нужно исключить бесконечное исполнение, которое навсегда остаётся в ожидании. В конечном произведении оно существует тогда и только тогда, когда достижим ориентированный цикл из ожидающих состояний, не заходя через успех или ошибку. Дойдя до цикла, можно повторять его бесконечно.
Почему доступность выхода не заставляет им воспользоваться
Пусть 0→1,2; 1→1,2; 2→2. В 0 и 1 истинно p и ложно q. В 2 истинно q и ложно p. Из любой вершины существует путь до q. Однако исполнение 0,1,1,1,… допустимо и никогда не использует выход 1→2.
Неявная фраза «рано или поздно система выберет выход» добавила бы предположение о справедливости. В исходной модели его нет. Если удалить самопетлю 1→1, все пути из 0 достигают 2 максимум за два перехода, и обязательство уже доказуемо. Это изменение рёбер, а не косметическая замена названия временного оператора.
Достижимая цель и бесконечное ожидание
Условие. Для графа 0→1,2; 1→1,2; 2→2, P={0,1},Q={2} проверьте всеобщее p U q из 0. Постройте контрпример и укажите результат после удаления ребра 1→1.
- После наблюдения 0 монитор ждёт. Переход в 1 сохраняет ожидание, а переход в 2 закрывает обязательство успехом, несмотря на ложность p в 2.
- В произведении достижимо состояние (1,ждём) с самопетлёй. Его можно посещать бесконечно, не наблюдая q.
- Контрпример состоит из префикса 0 и цикла 1: 0·1^ω. На нём p истинно всегда, но конечного номера первого q нет. Сильное until ложно.
- После удаления 1→1 подграф ожидания содержит только ребро 0→1 и не имеет цикла. Из 0 либо сразу попадаем в 2, либо через 1. До q условие p выполнено.
Ответ. В исходной модели всеобщее p U q ложно; свидетельство 0,1,1,… . Без самопетли 1→1 оно истинно из 0.
Проверка. Независимая проверка перечисляет простые ожидающие циклы. В исходном графе есть цикл [1]; в изменённом их нет. Отдельно проверяется отсутствие достижимого состояния ¬p∧¬q до успеха.
Где легко ошибиться. Не принимайте отсутствие конечной ошибки за доказательство eventual-условия. Бесконечный цикл ожидания нарушает сильное until даже без единственного ложного p.
Проверьте понимание
Вопросы к этой главе
Самопетля в цели 2 тоже является контрпримером?
Нет. При первом наблюдении q монитор уже переходит в успех. Позднейший цикл не отменяет состоявшееся конечное свидетельство until.
Как трактовать тупик системы?
Здесь граф тотален. Если исходная модель содержит завершение, нужно явно выбрать семантику, например бесконечное повторение последнего состояния. Тупик с p и без q при таком продолжении нарушает сильное until.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Workcraft: временные свойства и следы нарушений
Прочитаны определения strong/weak until и конечного представления бесконечных следов. Монитор трёх режимов, граф и удаление петли разобраны самостоятельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Теорема Майхилла — Нероуда: конечные классы продолжений строят минимальный автомат
Доказать эквивалентность регулярности конечности классов правой конгруэнции и построить канонический минимальный ДКА по классам продолжений.
Открыть темуЛемма о накачке: разбиение выбирает противник, а степень выбираете вы
Построить корректное доказательство нерегулярности языка по лемме о накачке, сохраняя порядок кванторов и охватывая все допустимые разбиения.
Открыть темуТеорема Райса относится к смыслу программы: синтаксический тест остаётся другой задачей
Распознать нетривиальное семантическое свойство вычислимой частичной функции и правильно применить неразрешимость, не распространяя её на свойства текста программы.
Открыть тему