Так как 3 - заключительное состояние, то ababa
Очевидно, что детерминированные конечные автоматы являются частными случаями недетерминированных. Естественно спросить, распознают ли недетерминированные конечные автоматы больший класс языков чем детерминированные? Следующая теорема показывает, что классы языков, распознаваемых НКА и ДКА совпадают.
Теорема 4.2. (Детерминизация НКА)
Для каждого НКА M можно эффективно построить такой ДКА A, что LA = LM.
Доказательство Пусть M= <?, Q, q0, F, ? > - НКА. Процедура построения по нему эквивалентного ДКА состоит из двух этапов: на первом по M строится эквивалентный ему НКА M1, в программе которого отсутствуют переходы по ?, а на втором этапе по M1 строится эквивалентный ДКА A.