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



             

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


Покажем, что тогда для некоторого w
L u =
(w). Рассмотрим для этого путь в диаграмме M из q0 в q'
FM, несущий слово u . Выделим на этом пути все состояния из Q. Пусть это будут по порядку состояния q0=q{j0}, q{j1}, … q{jk}= q'. Тогда слово u разбивается на k подслов: u=u1u2 … uk таких, что ux переводит в M состояние
 q_{j_{x-1}}
в
 q_{j_x}

(1

x
k). Покажем, что для каждого такого ux существует символ wx
? такой, что ux =
(wx) и в ? имеется команда
 q_{j_{x-1}} w_x \rightarrow q_{j_x}
. Действительно, любой путь из
 q_{j_{x-1}}
в M начинается ?-переходом в некоторое состояние вида
p_0^{j_{x-1}i}
. Пусть это будет состояние на пути, который несет ux в
 q_{j_x}
. Далее этот путь обязательно будет проходить по состояниям вида
p_l^{j_{x-1}i}\ (l=1,\ldots , k_i )
и завершится ?-переходом из
 p_{k_i}^{j_x i}
в состояние
 q_{j_x}
. Тогда из определения M следует, что ux =
(ai) и в ? имеется команда
 q_{j_{x-1}} w_x \rightarrow q_{j_x}
. Положив wx=ai, получим, что ux =
(wx) и u=
(w1)
(w2) …
(wk) =
(w), для слова w=w1w2 … wk
?*. При этом каждый символ wx этого слова переводит в автомате A состояние
 q_{j_{x-1}}
в
 q_{j_x}
. Поэтому в A существует путь из q0 в q'
F, несущий слово w и, следовательно w
L .




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