Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 38 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

40
Недетерминированный разбор
Как уже отмечалось, при анализе по регулярной грамматике может ока-
заться, что несколько нетерминалов имеют одинаковые правые части, и поэто-
му неясно, к какому из них делать свертку. В терминах диаграммы состояний
это означает, что из одного состояния выходит несколько дуг, ведущих в раз-
ные состояния, но помеченных одним и тем же символом. Такой грамматике
будет соответствовать недетерминированный конечный автомат.
Недетерминированный конечный автомат (НКА) – это пятерка (K,VT, δ,H,S),
где:
K – конечное множество состояний;
VT – конечное множество допустимых входных символов;
δ – отображение множества K × VT в множество подмножеств K;
H ∈ K – конечное множество начальных состояний;
S ∈ K – конечное множество заключительных состояний.
δ(A,t) = {B
1
,B
2
,...,B
n
} означает, что из состояния A по входному символу t мож-
но осуществить переход в любое из состояний B
i
, i = 1, 2, ... ,n.
Для недетерминированного конечного автомата можно предложить алго-
ритм, который будет перебирать все возможные варианты сверток (переходов)
один за другим; если цепочка принадлежит языку, то будет найден путь, веду-
щий к успеху; если будут просмотрены все варианты, и каждый из них будет
завершаться неудачей, то цепочка языку не принадлежит. Однако такой алго-
ритм практически неприемлем, поскольку при переборе вариантов мы, скорее
всего, снова окажемся перед проблемой выбора и, следовательно, будем иметь
дерево отложенных вариантов.
Один из наиболее важных результатов теории конечных автоматов состоит
в том, что класс языков, определяемых недетерминированными конечными ав-
томатами, совпадает с классом языков, определяемых детерминированными
конечными автоматами. Это означает, что для любого НКА всегда можно по-
строить детерминированный КА, определяющий тот же язык.
Алгоритм построения детерминированного КА по НКА
Вход: M = (K, VT, δ, H, S) – недетерминированный конечный автомат.
Выход: M' = (K', VT, δ', H', S') – детерминированный конечный автомат,
допускающий тот же язык, что и автомат М.
1. Множество состояний К' состоит из всех подмножеств множества К.
Каждое состояние из К' будем обозначать [A
1
A
2
...A
n
], где A
i
∈ K.
2. Отображение δ' определим как δ' ([A
1
A
2
...A
n
], t) = [B
1
B
2
...B
m
], где для
каждого 1 ≤ j ≤ m δ(A
i
, t) = B
j
для каких-либо 1 ≤ i ≤ n.
3. Пусть H = {H
1
, H
2
, ..., H
k
}, тогда H' = [H
1
, H
2
, ..., H
k
].
4. Пусть S = {S
1
, S
2
, ..., S
p
}, тогда S' – все состояния из K', имеющие вид
[...S
i
...], .S
i
∈ S для какого-либо 1 ≤ i ≤ p.
В множестве K' могут оказаться состояния, которые недостижимы из на-
чального состояния, их можно исключить.

Страницы