Языки и трансляции. Мартыненко Б.К. - 43 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

42
множество всех цепочек, которые переводят fa M из состояния q
i
в состояние
q
j
, не проходя через какое-либо состояние q
l
, где l > k. Заметим, что под
“прохождением через состояние” мы
подразумеваем вход и выход вместе. Но
сами i и j могут быть больше k.
Мы можем определить
k
ij
R
рекурсивно:
которые переводят автомат M из состояния q
i
в состояние q
j
без перехода через
состояния выше, чем q
k
, либо находятся во множестве
1k
ij
R
−
, т.е. никогда не
приводят автомат в состояние столь высокое, как q
k
, либо каждая такая цепочка
состоит из цепочки во множестве
1k
ik
R
−
(которая переводит автомат M в
состояние q
k
первый раз), за которой следует сколько-то цепочек из множества
1k
kk
R
−
, переводящих автомат M из состояния q
k
снова в состояние q
k
без перехода
через состояние q
k
и высшие состояния, за которыми следует цепочка из
множества
1k
j
k
R
−
, переводящая автомат M из состояния q
k
в состояние q
j
,
который при этом опять же не достигает состояния q
k
и не проходит состояний
с большими номерами.
Индукцией по параметру k мы можем показать, что множество
k
ij
R
для всех
i и j находятся в пределах класса
M.
База. Пусть k = 0. Утверждение
очевидно, поскольку все множества
0
ij
R
являются конечными.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех k, таких, что 0 ≤ k ≤ m (0 ≤ m < n).
Индукционный переход. Докажем, что утверждение верно и для
k = m +1.
Это так, поскольку
1m
ij
R
+
выражается
через объединение, конкатена-
цию и
замыкание различных множеств вида
m
pq
R
, каждое из которых по индук-
ционному предположению находится в классе
M.
Остаётся заметить, что .
Таким образом, множество L
1
находится в классе M — наименьшем классе
множеств, содержащем все конечные множества, замкнутом относительно
объединения, конкатенации и замыкания. Что и требовалось доказать.
Следствие 3.1 (из теоремы Клини). Из теоремы 3.11 следует, что любое
выражение, построенное из конечных подмножеств множества Σ
*
, где Σ —
конечный алфавит, и конечного числа операций объединения
‘∪’,
произведения и замыкания
‘
*
’ со скобками, которые определяют порядок
действий, обозначает множество, принимаемое некоторым конечным
автоматом. И наоборот, каждое множество, принимаемое некоторым конечным
автоматом, может быть представлено в виде такого выражения. Это
обеспечивает нас хорошим средством для описания регулярных множеств. Оно
называется регулярным выражением.
1
1
j
n
j
qF
LR
∈
=
∪
0
{,(,)}.
,
ij
ij
aqaq
R
=∈Σδ =
*
11
11
()
kk k
kk
ij ij
j
ik kk k
RR RR R
−−
−−
=∪

Страницы