Конечные автоматы
Доказательство. По теореме 1 L допускается некоторым
НКА М = (S, I, 1б 0, 1s0 0, { 1Sf 0}). Превратим М в ДКА следующим
образом. Сначала найдем такие пары состояний 1(s, t) 0, что
1(s, e) 0├─ м* 1(t, e) 0. Чтобы сделать это, построим ориентиро-
ванный граф G = (S, E), у которого 1(s, t) 0принадлежит Е
тогда и только тогда, когда 1б(s, e) 0содержит 1t 0. Затем вы-
числим рефлексивное и транзитивное замыкание G' = (S, E')
графа G. Мы утверждаем, что 1(s, e) 0├─ м* 1(t, e) 0тогда и
только тогда, когда 1 (s, t) 0 принадлежит Е'.
Теперь построим такой НКА М' = (S', I, 1б 0', 1s0 0, F), что
L(M') = L(M) и в М' нет 1 е 0- переходов.
1) 1S' = {s0} U {t│б(s, a) 0содержит 1t 0для некоторого 1s
(- S и некоторого 1а 0(- I 1} 0.
2) Для каждого 1 s 0 (- S' и каждого 1 а 0 (- I
1б'(s, a) = {u│(s, t) 0 (- E' и 1 б(t, a) 0 содержит 1 u} 0.
3) F' = 1 {s│(s, f) 0 (- E' и 1 f 0 (- F 1} 0.
Таким образом L(M) = L(M') и в M' нет переходов по 1 е 0.
Далее по M' построим ДКА M'', состояния которого обра-
зуют множество-степень для S'. Другими словами, M'' =
( 1P 0(S'), I, 1 б'' 0, { 1s0 0}, F''), где
1) для каждого подмножества S множества S' и каждого 1а
(- I
1б''(S, a) = {t│б'(s, a) 0содержит 1t 0для некоторого 1s 0(-
S 1} 0,
2) F'' = {S│S П F <> (/)}.
Далее с помощью индукции по │ 1w 0│, можно доказать, что
( 1{s0}, w) 0├─ м*''(S, 1e 0) тогда и только тогда, когда S =
1{t│(s0, w) 0 ├─ м*' 1(t, e)} 0.
Следовательно L(M) = L(M') = L(M''). Что и требовалось
доказать.
4. Пример преобразования НКА в ДКА
На основе приведенного выше доказательства, рассмотрим
пример для произвольного НКА М (рис. 3). Приведем его из
недетерминированного вида в детерминированный аналог.
1b
┌──────────────────────────────────────┐
│ │
│ ┌─────┐ 1a 0 │
│ ┌──────│ 1s2 0 │───────────────┐ │
│ │ 1a 0 └────┬┘ │ v
┌──┴──┐ │ 1 0 ^ │ 1e 0 ┌=====┐
│ 1s1 0 ├──┘ │ └───────────────│ 1s4 0 │
└──┬──┘ │ └=====┘
│ │ ^
│ │ │
│ 1e 0 │ │
│ │ │
│ │ │
│ ┌──┴──┐ 1e 0 │
└────────────│ 1s3 0 ├──────────────────┘
└─────┘
Рис. 3. Пример недетерминированного автомата НКА М
Из начального состояния s1 можно достичь s3 и заключи-
тельное состояние s4 по путям, помеченным символом 1е 0. Поэ-
тому для вычисления рефлексивного и транзитивного замыкания
G' ориентированного графа G, о котором шла речь в доказа-
тельстве теоремы 3, надо добавить ребро (s1, s4).
Весь граф G' изображен на рис. 4. По М и G' построим
НКА М' (рис. 5). Так как в узел s4 входят ребра из всех уз-
лов графа G', то обьявляем все состояния в М' заключитель-
ными.
┌─────┐
│ │ ┌─────┐
│ v │ │
│ ┌─────┐ ┌──┴──┐ │
└──┤ 1s1 0 ├──────────┐ │ 1s2 0 │─┘
└──┬──┘ │ └──┬──┘
│ │ │
│ │ │
│ │ │
│ │ │
│ └─────────────────┐ │
v v v
┌─────┐ ┌─────┐
┌─│ 1s3 0 ├──────────────────────────│ 1s4 0 ├──┐
│ └──┬──┘ └─────┘ │
│ │ ^ │