Замкнутость относительно гомоморфизмов и их обращений - часть 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

ki) (если

(ai)

?). Для каждого ai зафиксируем простой НКА Mi, распознающий язык {d1id2i … d{ki}i}, имеющий (ki +1) состояние p0i, p1i, …, p{ki}i и команды p{l-1}dli

pl (1

ki). ( Если

(ai) = ?, то у Mi будут два состояния, соединенные ?-переходом). Теперь для каждой команды qj ai

qr поместим в M между qj и qr автомат Mi (цепочку состояний p0i, p1i, …, p{ki}i). Чтобы состояния различных цепочек не склеивались, придадим им верхний индекс j, т.е. у каждого qj будет своя копия каждого из автоматов Mi. Для этого положим QM = Q

{ plji | 0

n, 1

m, 0

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 .

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

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

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