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


           

Выделим на этом пути все


Покажем, что тогда для некоторого 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 состояние
в


(1
x
k). Покажем, что для каждого такого ux существует символ wx
? такой, что ux =
(wx) и в ? имеется команда
. Действительно, любой путь из
в M начинается ?-переходом в некоторое состояние вида
. Пусть это будет состояние на пути, который несет ux в
. Далее этот путь обязательно будет проходить по состояниям вида
и завершится ?-переходом из
в состояние
. Тогда из определения M следует, что ux =
(ai) и в ? имеется команда
. Положив wx=ai, получим, что ux =
(wx) и u=
(w1)
(w2) …
(wk) =
(w), для слова w=w1w2 … wk
?*. При этом каждый символ wx этого слова переводит в автомате A состояние
в
. Поэтому в A существует путь из q0 в q'
F, несущий слово w и, следовательно w
L .


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