Конечные автоматы

кается некоторым ДКА.


Доказательство. По теореме 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 ├──┐

│ └──┬──┘ └─────┘ │

│ │ ^ │

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: