Конечные автоматы
Рис. 4. Граф G'
Так единственное ребро, входящее в узел s3 в диаграмме
для М, помечено символом 1 е 0, то s3 не входит в М'.
1b
┌───────────────────────────────────┐
│ v
┌=====┐ 1 a,b 0 ┌=====┐ 1a 0 ┌=====┐
│ 1s1 0 ├───────────│ 1s2 0 │─────────┤ 1s4 0 │
└=====┘ └=====┘ └=====┘
│ ^
└───┘
1a
Рис. 5. НКА М'
При построении ДКА М'' по автомату М' образуется восемь
состояний. Но только четырех из них можно достичь из на-
чального состояния, так что остальные четыре можно выбро-
сить.
Приведенный к детерминированному виду автомат М'' при-
веден на рис. 6.
Таким образом было показана возможность приведения НКА
к ДКА. При такой операции число получившихся состояний мо-
жет существенно увеличиться, некоторые из них становятся
бесполезными. Сущность приведения заключается в том, что мы
ищем обходные пути для достижения конечного состояния,
стремясь к тому, чтобы исчезла неоднозначность перехода из
состояния в состояния в зависимости от входного символа.
Эта операция порождает несущественные состояния и поэтому,
видимо, в каждом из отдельных случаев решать задачу нужно
исходя их конкретных целей.
1b 0 ┌=======┐ 1 b
┌────────────────│ 1{s2,s4} 0├─────────────┐
│ └=======┘ v
│ │ ┌─────┐
│ │ 1a 0 │ 1(/) 0 │──┐
┌=====┐ │ └────┬┘ │
│ 1{s1} 0 │ │ ^ │ │
└=====┘ v │ └────┘
│ 1a 0 ┌=====┐ 1b 0 │ 1 a,b
└────────────────│ 1{s2} 0 ├───────────────┘
└=====┘
^ │
└───┘
1b
Рис. 6. ДКА G''
Для примера оценки стоимости преобразования НКА в ДКА
рассмотрим задачу распознавания образов, в которой дана це-
почка-текст x = a1 a2 ... an и регулярное выражение 2а 0, на-
зываемое образом. Мы хотим найти такой наименьший индекс j,
что для некоторого i подцепочка ai ai+1 ... aj цепочки x
принадлежит языку, представленному выражением 2 а 0.
Вопросы такого рода часто возникают при редактировании
текстов. Многие программы для редактирования текстов разре-
шают пользователю задавать типы замен в цепочке-тексте.
Например пользователь может сказать, что он хочет заменить
слово y каким-то другим словом в куске текста х. Чтобы вы-
полнить такую операцию, программа редактирования текста
должна суметь найти вхождение слова у в текст х. Некоторые
мощные редактирующие программы позволяют пользователю в ка-
честве множества заменяемых цепочек указывать регулярное
множество. Например пользователь может сказать: "Заменить
[I*] в х пустой цепочкой", имея в виду, что в х следует
стереть пару квадратных скобок и символы между ними.
Поставленную выше задачу можно переформулировать, заме-
нив данное регулярное выражение 2а 0выражение 2b 0= I* 2a 0, где I
- алфавит цепочки-текста. Можно найти первое вхождение це-
почки из L( 2a 0) в х = а1 а2 ... аn, обнаружив кратчайший пре-
фикс цепочки х, принадлежащий языку выражения 2b 0. Эту задачу
можно решить, построив НКА М для распознавания множества,
представленного выражением 2b 0, а затем определить множество
состояний в которые может перейти НКА М при прочтении це-
почки а1 а2 ... аn.
Один из способов моделирования поведения НКА М на це-
почке-тексте х - превратить М в детерминированный конечный
автомат, используя теорему 3. Однако такой путь окажется
достаточно дорогостоящим, поскольку от регулярного выраже-
ния 2b 0можно перейти к НКА с 2│ 2b 0│ состояниями, а затем к ДКА
с почти 2 в степени 2│ 2b 0│ состояниями.
Таким образом уже само построение ДКА может вызвать
непреодолимые трудности.