Недетерминированные конечные автоматы и их детерминизация - часть 3

$(0,ababa) \vdash_{N_1}(1, baba)\vdash_{N_1}(4, baba)\vdash_{N_1}(2, aba) \vdash_{N_1}(0, aba)\\ \vdash_{N_1}(1, ba)\vdash_{N_1}(4, ba)\vdash_{N_1}(2, a) \vdash_{N_1}(3,\varepsilon).$

Так как 3 - заключительное состояние, то ababa

LN1. Заметим, что у автомата N1 имеются и другие способы работы на этом слове, не ведущие к заключительному состоянию. Например, он может после чтения каждого символа оставаться в состоянии 0. Но чтобы слово допускалось, достаточно существовать хотя бы одному "хорошему" способу.

Очевидно, что детерминированные конечные автоматы являются частными случаями недетерминированных. Естественно спросить, распознают ли недетерминированные конечные автоматы больший класс языков чем детерминированные? Следующая теорема показывает, что классы языков, распознаваемых НКА и ДКА совпадают.

Теорема 4.2. (Детерминизация НКА)

Для каждого НКА M можно эффективно построить такой ДКА A, что LA = LM.

Доказательство Пусть M= <?, Q, q0, F, ? > - НКА. Процедура построения по нему эквивалентного ДКА состоит из двух этапов: на первом по M строится эквивалентный ему НКА M1, в программе которого отсутствуют переходы по ?, а на втором этапе по M1 строится эквивалентный ДКА A.

Содержание Назад Вперед