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

5.7.2. Построение немшшмальвого графа переходов Ряс. 5.11. Дерево поиска состояний после конкретизации начальной последовательности а4а3а2а, 125 Для того чтобы можно было от построенного дерева на рис. 5.10 перейти к неминимальному графу переходов, будем полагать, что нам известна подпоследовательность а4а3а2а,, в результате которой автомат попал в состояние Ьо. Вообще это может быть любая подпоследовательность из числа допустимых. Пусть это будет подпоследовательность 0000. Тогда во всех подпоследовательностях дерева, показанного на рис. 5.10, символ «?» следует заменить на 0. В результате получим дерево, показанное на рис. 5.11. Каждой вершине этого дерева соответствует одна конкретная подпоследовательность а4а3а2а,, состоящая из 0 и 1. Все конкретные подпоследовательности встречаются на дереве. Дерево, представленное на рис. 5.10, может быть продолжено,, поскольку-на автомат подается бесконечная последовательность из 6 и 1. Но новых подпоследовательностей и соответствующих им состояний уже не появится. Дня каждого из состояний на дереве рис. 5.10, из которого дуги $ще не выходят, найдется уже полученное состояние, в которое из этого состояния может быть направлена дуга. Поэтому нет смысла продолжать построение дерева, а во-вторых, можно удалить те поддеревья, которые начинаются в состояниях, встречающихся повторно, перенаправив идущие к этим поддеревьям дуги в ранее встречающиеся состояния. В результате из дерева на рис. 5.11 получится граф переходов, показанный на рис. 5.12.