Реализация конечного недетерминированного автомата

Snake!

У меня недавно появилась необходимость в реализации сабжа. Есть ли у кого-нибудь соображения по поводу написания КНА?
Вообще я думал для каждого состояния сделать свой класс и каким-либо образом по ним бегать. Скорее всего нужен будет ещё один класс перехода. Но это пока только общие мысли.

Alexey · 27.11.2005 2:13

Тебе необходимо именно сымитировать работу недетерминированного конечного автомата или
построить автомат выполняющий аналогичные задачи (в теории их вычислительная мощность одинакова).

Если ставится первая задача то здесь все достаточно просто при каждой неоднозначности разветляем
процесс и если в каком то из процессов строка обрабатываемая автоматом принята ... (автомат перешел
в завершающее состояние) то эта строка допускается данным автоматом. Этот способ не самый оптимальный
так как работает очень долго.

Намного проще реализовать вторую задачу, в частности преобразовать недетерминированный автомат
в детерминированный и сымитировать работу уже детерминированного автомата.
Алгоритм преобразования немного =) грамозок:
Если у нас есть начальные состояния {1,2,...n} необходимо сгенирировать состояния нового
(детерминированного) автомата, их будет столько сколько подмножеств у множества начальных состояний
Например если изначальный автомат имеет состояния {1,2,3} то получатся следущие состояния:
{1}
{2}
{3}
{1,2}
{2,3}
{1,3}
{1,2,3}
Далее составляем множество всех достижимых по некоторому символу состояний, тоесть
если из состояния 1 по символу A можно попасть в 2 и 3 то получаем
P(1,A) -> {2,3}
и т.д для всех вершин и входных символов.
Стартовым состоянием нового автомата будет стартовое состояние исходного автомата,
допускающим все состояния содержащие допускающие сосотояние исходного автомата.
Если исходный автомат содержит состояния {1,2,3} 1-стартовое, 3-допускающие
то для нового автомата стартовым будет состояние {1},
допускающими {3},{2,3},{1,3},{1,2,3}

Далле выполняем следующий алгоритм:

Для каждого состояния {S1,S2,....Sn} создаваемого автомата
{
Для каждого символа входного алфавита ( С )
{
R={};
Для каждого элемента Si
R=R обьединись с P (Si,C);
Добавить в новый автомат правило {S1,...Sn},C -> R;
}
}

Минимизируем полученный автомат и моделируем его работу.

Snake! · 27.11.2005 2:57

Ого!

Даже не ожидал, что кто-то так развёрнуто ответит.
Спасибо огромное!

Добавлено спустя 3 минуты 14 секунд:

Хм... получается, что в первом способе возвраты назад не допускаются! А должны.
Нужен-то именно он.

Alexey · 27.11.2005 5:49

Можно реализовать рекрусивной функцией
такого рода

просмотр
{
если символов входной ленты не осталось :
1) если автомат в завершающем состоянии ... строка принята
2) иначе строка не принята

если есть неоднозначность
__сначала иди по первому варианту, затем по второму и т.д
____если какой нибуть из вариантов пернул что строка принята
_____завершаем работу строка принята...
если нет переходи в ледующие состояние по данному символу
}

есть замечательнкая книжечна В.М Мозговова
Алгоритмы, Языки, Автоматы. Компиляторы.
там это все на С# уже написано ctrl+c,ctrl+v

Snake! · 27.11.2005 23:18

Alexey
Ну я примерно так изначально и думал =)

А ctrl-c, ctrl-v не получится, т.к. надо с исп. абстрактных классов писать прогу. Это обязательное условие.

Кстати, а ты вообще из ГУАПа?

Alexey · 28.11.2005 8:20

Да ..., но раньше я сюда не заходил ... чуть другая специализация была (учился на 2016 счас перевелся на 3515) если бы меня на второй год не оставили Смайлик

учился б с тобой на одним потоке ...

Snake! · 28.11.2005 9:35

Alexey
Ты бы был ща в 4366 =)

Pauls · 01.12.2006 23:07

Snake! писал(а):

Вообще я думал для каждого состояния сделать свой класс и каким-либо образом по ним бегать. Скорее всего нужен будет ещё один класс перехода. Но это пока только общие мысли.

думается мне что задачка решается с помощъю матрицы переходов и функции которая собственно этот переход и осуществляет Ж)
...не плодите сущности сверх необходимого

	Список форумов FREESTUDENTS -> Архив	Часовой пояс: GMT + 3
Страница 1 из 1