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



             

Замкнутость относительно гомоморфизмов и их обращений - часть 2


Доказательство Пусть 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 следующие команды:

 q_j \rightarrow p_0^{ji},\\ p_0^{ji}d_1^i \rightarrow p_1^{ji},\\ \bullet \ \bullet\ \bullet \\ p_{k_i-1}^{ji}d_{k_i}^i \rightarrow p_{k_i}^{ji},\\ p_{k_i}^{ji} \rightarrow q_r

Таким образом, из 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. Пусть это путь
    q_0=q_{j_0}, q_{j_1}, \ldots q_{j_k}= q^\prime
    . Тогда для каждого 1
    x
    k в ? имеется команда
     q_{j_{x-1}} w_x \rightarrow q_{j_x}
    . Но из определения ?M следует, что тогда в автомате M имеется путь из
     q_{j_{x-1}}
    в
     q_{j_x}
    , несущий слово
    (wx). Объединив все такие пути, получим путь из из q0 в q'
    FM, несущий слово
    (w). Следовательно,
    (w)
    LM.

  2. LM

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


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