Искусственный интеллект

Класс С?/0' в этом случае можно разбить на два подкласса {е, а2аг) и {а2, alalal, о,о,о2}, так как с,, (р%еа2) = ^\а2а2а2) = су = фЧо,о,о,о,) = <р «Цо^о,) =с2, су Введем новые обозначения классов G«> = {e, а2а2), С?2(1) = {о,, с,о2, аха2а2, а2а2ах), Q™ = {alal, a2av ata2av axafixax, 0,0,0^,}, G4(I> = {c2, 0,0,0,, o,o,o2}. Эти классы совпадают соответственно с классами Qv Qv Q3, QA, полученными по алгоритму разбиения последовательности на классы эквивалентности и," следовательно, автомат М,(|), который можно построить по этим классам, является детерминированным. Настоящим примером был проиллюстрирован подход к процедуре детерминизации. Перейдем к более строгой формулировке этой процедуры в виде алгоритма. Рассмотрим отношение Е1П на множестве А*": о, *?<'>с2 * если с,*, о2*е А*", ф*(о,*с*) = ф*(с2*о*) для всех о* е А*" длиной /(о*) < /. Из определения отношения Еи) следует, что отношение Ет как раз разбивает множество последовательностей Р из рассмотренного примера на классы QfK (?2<0). (?э(0)- Действительно отношение Е(0) проверяется только для последовательностей о*, длина которых равна нулю, а такая последо¬вательность существует только одна — пустая последовательность е. Тогда по определению ?('} для любых двух последовательностей с, *, а2 * е Р имеет место а, *Е(0)а2 *, если ф \а1 *) — ц> \а2 *). В то же время , если i выбрано равным или большим длине г\ самой длинной входной последовательности из множества Р, то из определения отношения Ein следует, что отношение Ем совпадает с отношением R, а отношение E(i+l) разбивает множество Р на классы, каждый из которых является подклассом отношения №ь т.е. для каждого класса QjM) существует класс QJ'}, такой, что ^<Ж)? Q^-.B общем случае автомат А/(1) = (А, В(1>, С{1>, /<0, ф(0) строится аналогично автомату