Детерминизация НКА с ε-переходами

Построить достижимые состояния ДКА как множества состояний НКА и проверить короткое двоичное слово с учётом ε-замыканий.

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

Слово принимается

Проверяемые промежуточные данные
ДКАМножество НКАПо 0По 1Принимающее
0[0, 1]12False
1[1]12False
2[2]32True
3[]33False
  1. Построены только достижимые подмножества, включая достижимое пустое.
  2. ε-переходы не потребляют символ входного слова.

Метод и условия расчёта

Перед чтением и после каждого символа берём ε-замыкание.

Состояние ДКА принимающее, если его множество содержит хотя бы одно принимающее состояние НКА.

Теория к методу

Состояние детерминированного автомата — множество возможных состояний исходного НКА. Перед чтением и после каждого символа добавляют ε-замыкание. Подмножество принимающее, когда в нём существует хотя бы одно принимающее состояние НКА.

Вначале уточните алфавит. Здесь входные символы — ноль и единица, а метка два в таблице переходов обозначает ε, то есть движение без чтения символа. Это служебная метка таблицы, она не становится третьей буквой входного слова. Начальное состояние ДКА содержит начальное состояние НКА и все вершины, доступные из него одними ε-переходами.

Пример: Пусть из 0 есть ε-переход в 1, состояние 1 повторяет нули и по единице переходит в принимающее 2, а 2 повторяет единицы. Для слова 0011 последовательность множеств начинается с {0,1}, затем дважды {1}, затем дважды {2}.

Слово принимается. Пустое слово отвергается, поскольку начальное замыкание не содержит 2. Для слова 10 после единицы окажемся в {2}, а по нулю перейдём в пустое множество.

Вопросы по теме

Пустое множество можно не показывать?

Если оно достижимо, это обычное отвергающее состояние ДКА; оно сохраняется в таблице.

Множество принимающее лишь при принятии всеми вершинами?

Нет. НКА принимает при существовании хотя бы одного принимающего пути.

Методы алгоритмов: углубление: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.