Детерминизация НКА с ε-переходами
Построить достижимые состояния ДКА как множества состояний НКА и проверить короткое двоичное слово с учётом ε-замыканий.
Ваш пример
Разбор примера
Слово принимается
| ДКА | Множество НКА | По 0 | По 1 | Принимающее |
|---|---|---|---|---|
| 0 | [0, 1] | 1 | 2 | False |
| 1 | [1] | 1 | 2 | False |
| 2 | [2] | 3 | 2 | True |
| 3 | [] | 3 | 3 | False |
- Построены только достижимые подмножества, включая достижимое пустое.
- ε-переходы не потребляют символ входного слова.
Метод и условия расчёта
Перед чтением и после каждого символа берём ε-замыкание.
Состояние ДКА принимающее, если его множество содержит хотя бы одно принимающее состояние НКА.
Теория к методу
Состояние детерминированного автомата — множество возможных состояний исходного НКА. Перед чтением и после каждого символа добавляют ε-замыкание. Подмножество принимающее, когда в нём существует хотя бы одно принимающее состояние НКА.
Вначале уточните алфавит. Здесь входные символы — ноль и единица, а метка два в таблице переходов обозначает ε, то есть движение без чтения символа. Это служебная метка таблицы, она не становится третьей буквой входного слова. Начальное состояние ДКА содержит начальное состояние НКА и все вершины, доступные из него одними ε-переходами.
Пример: Пусть из 0 есть ε-переход в 1, состояние 1 повторяет нули и по единице переходит в принимающее 2, а 2 повторяет единицы. Для слова 0011 последовательность множеств начинается с {0,1}, затем дважды {1}, затем дважды {2}.
Слово принимается. Пустое слово отвергается, поскольку начальное замыкание не содержит 2. Для слова 10 после единицы окажемся в {2}, а по нулю перейдём в пустое множество.
Вопросы по теме
Пустое множество можно не показывать?
Если оно достижимо, это обычное отвергающее состояние ДКА; оно сохраняется в таблице.
Множество принимающее лишь при принятии всеми вершинами?
Нет. НКА принимает при существовании хотя бы одного принимающего пути.
Методы алгоритмов: углубление: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.