46030 (665337), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Поставленную выше задачу можно переформулировать, заме-

нив данное регулярное выражение 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│ состояниями.

Таким образом уже само построение ДКА может вызвать

непреодолимые трудности.

Характеристики

Список файлов реферата