распознающий язык L. Построим по
Доказательство Пусть A=<?, Q, q0, F, ?> - ДКА, распознающий язык L. Построим по нему НКА M =<?, QM, q0M, FM, ?M>, распознающий язык
(L). Идея этого построения проста: нужно каждый переход из состояния q в q' по букве a
? в автомате A превратить в переход из q в q' по слову
(a) в автомате M.
Пусть ? = {a1, … , am}, Q= {q0, q1, …, qn} и
(ai)= d1id2i … d{ki}i, dli
? (1
l
ki) (если
(ai)
?). Для каждого ai зафиксируем простой НКА Mi, распознающий язык {d1id2i … d{ki}i}, имеющий (ki +1) состояние p0i, p1i, …, p{ki}i и команды p{l-1}dli
pl (1
l
ki). ( Если
(ai) = ?, то у Mi будут два состояния, соединенные ?-переходом). Теперь для каждой команды qj ai
qr поместим в M между qj и qr автомат Mi (цепочку состояний p0i, p1i, …, p{ki}i). Чтобы состояния различных цепочек не склеивались, придадим им верхний индекс j, т.е. у каждого qj будет своя копия каждого из автоматов Mi. Для этого положим QM = Q
{ plji | 0
j
n, 1
i
m, 0
l
ki }. Таким образом, pl{ji} - это l-ое состояние на пути из qj по "старой" букве ai. Программа ?M автомата M строится по программе A следующим образом. Для каждой команды вида qj ai
qr из ? поместим в ?M следующие команды:
Таким образом, из qj автомат M по пустому переходу попадает в начальное состояние p0ji j-ой копии автомата Mi, затем проходит по слову
(ai) и снова по пустому переходу попадает в qr.
Для завершения определения M положим q0M = q0 и FM = F.
Докажем теперь, что наше построение корректно, т.е., что
(L)=
( LA) = LM .
(L) LM. Заметим вначале, что если ? L, то q0 F и по определению q0 FM, следовательно (?)=? LM.
Пусть w=w1w2… wk L, ws ?. Тогда в диаграмме A имеется путь из q0 в некоторое заключительное состояние q' F, который несет слово w. Пусть это путь . Тогда для каждого 1 x k в ? имеется команда . Но из определения ?M следует, что тогда в автомате M имеется путь из в , несущий слово (wx). Объединив все такие пути, получим путь из из q0 в q' FM, несущий слово (w). Следовательно, (w) LM.
LM (L). Пусть слово u ?* принадлежит LM.
Содержание Назад Вперед