Преобразование НКА в ДКА

Алгоритм моделирования ДКА

Вход. ДКА A; входная строка, завершаемая символом конца файла eof.

Выход. «Да», если ДКА A допускает , «Нет» в противном случае.

Метод.

move(S, C) - функция переходов, возвращает состояние, в которое происходит переход из состояния при входном символе .

nextchar – функция, которая возвращает очередной символ входной строки .

Пример. Граф переходов ДКА, допускающий тот же язык , что и ранее приведенный НКА.

Алгоритм, который мы рассмотрим, называется построением подмножества.

Предварительные замечания.

В таблице переходов НКА каждая клеточка представляет собой некоторое подмножество состояний, в ДКА – единственное состояние. Общая идея преобразования НКА в ДКА состоит в том, что каждое состояние ДКА моделирует некоторое подмножество состояний НКА. ДКА использует свои состояния для отслеживания всех возможных состояний, в которых НКА может находиться после прочтения очередного входного символа. Таким образом, после чтения входной строки ДКА находится в состоянии, которое моделирует подмножество состояний НКА, достижимых из начального состояния НКА по путям, отмеченным .

Количество состояний ДКА может оказаться экспоненциально зависящим от количества состояний НКА. Это наихудший случай. На практике встречается редко.

Для отслеживания подмножества состояний НКА нам понадобятся некоторые вспомогательные операции.

Пусть состояние НКА, подмножество состояний НКА.

1. замыкание состояния: обозначение замыкания

подмножество состояний НКА, достижимых из состояния только по переходам. Само включено в .

2. замыкание подмножества . Обозначение .

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

3. подмножество состояний НКА, в которые имеется переход из какого-либо состояния из по входному символу .

Вычисление является типичным процессом поиска в графе тех узлов, которые достижимы из заданного подмножества узлов. В этом случае состояния подмножества представляют заданное подмножество узлов, а граф состоит только из дуг НКА, помеченных .

Алгоритм построения ДКА из НКА («ленивое» вычисление подмножеств)

Изначально таблица переходов ДКА содержит только одно состояние - . Это состояние объявляется текущим подмножеством .

Для текущего состояния по каждому символу из входного алфавита строим подмножество .

Тем самым происходит заполнение текущей строки в таблице переходов ДКА. Если при этом образуются новые подмножества, те, которые еще не включены в эту таблицу, то дописываем их в новую строку как еще одно состояние ДКА.

Процесс останавливается после заполнения всей таблицы. В построенной таблице строка, соответствующая , объявляется начальным состоянием для ДКА.

Заключительными объявляются те из полученных подмножеств, в состав которых входит хотя бы одно из заключительных состояний исходного НКА.

Пример.

НКА, допускающий язык, строки которого оканчиваются на 011 и соответствующий ДКА.

→ 01247				→ A	B	C
				B	B	D
				C	B	C
		124567,10		D	B	E
124567,10				* E	B	C

Дата добавления: 2013-12-14