Стр. 19 - Информационные структуры и их преобразование

Содержание 17
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
δ(S0)=V,Q; δ(S1)=U,Q; δ(Q0)=V,Q; δ(Q1)=U,Q;
δ(U1)=Z; δ(V0)=Z; δ(Z1)=Z; δ(Z0)=Z.
Предположим, у нас есть цепочка 01001. Рассмотрим ее разбор по
шагам:
Шаг Текущее состояние Остаток входной
цепочки
Возможные
состояния
Выбранное
состояние
1 S 01001 V,Q Q
2 Q 1001 U,Q Q
3 Q 001 V,Q V
4 V 01 Z Z
5 Z 1 Z Z
Для любой регулярной грамматики G можно построить диаграмму
состояний, а следовательно, НКА. При работе НКА возникает
неоднозначность при выборе следующего состояния, если существуют
несколько дуг с одинаковой пометкой. Поэтому, прежде чем прийти к выводу
о том, что строка не может быть принята НКА, необходимо перепробовать
всевозможные последовательности переходов. Следовательно, читать
входную цепочку необходимо не один раз, а ∏( ni ) , где n-число возможных
переходов на j шаге.
Пусть мы имеем НКА {Q, Σ, δ, S, Z}. Нужно построить ДКА
{Q’ Σ, δ’, S’, Z’}.
0 0
1 0 0
1
1 0
W
N