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

16 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
δ – функция отображения ( Q×Σ → Q );
S – начальное состояние;
Z– конечное состояние.
Будем говорить, что ДКА допускает цепочку t , если δ (St)=P, где Р ∈Z.
Можно переписать правила из примера следующим образом:
δ (U0)=Z , δ (V1)=Z , δ (Z1)=U , δ (S1)=U , δ (Z0)=V , δ (S0)=V.
ДКА с состояниями Si и входной литерой tj можно представить
матрицей B=||bij||, элемент которой bij=k, где k – номер состояния, и
существуют функции отображения δ ( Si , tj )=Sk .
U V
ош. Z U
Z ош. V
U V Z
1 0
S - 1 0 - S
- - - 0U
- - - 1V
- 1 0 - Z
SUVZ
Недетерминированные конечные автоматы
Положение осложняется, если грамматика G содержит правила вида:V:
= UT; W: = UT, то есть одинаковые правые части. В диаграмме состояний
есть 2 дуги, помеченные символом Т, исходящих из U. Отображение δ
становится неоднозначным, и поэтому автомат становится
недетерминированным.
Пример:
НКА { Q , Σ , δ , S , Z }, δ(RT) = { Wi }, где Wi ∈Q.
Напишем правила через функцию отображения:
S Z
U
V
1
1
1
0
0 0
0
Q 1
1 1 0 0