Введение в схемы, автоматы и алгоритмы

             

распознающий язык 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 .



  1. (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.



  2. LM
    (L). Пусть слово u
    ?* принадлежит LM.

    Содержание  Назад  Вперед