Форум программистов
 
Регистрация на форуме тут, о проблемах пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Как купить рекламу на форуме


Вернуться   Форум программистов > Delphi программирование > Общие вопросы Delphi
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 05.10.2008, 23:23   #1
Arkuz
Форумчанин
 
Аватар для Arkuz
 
Регистрация: 22.09.2007
Сообщений: 538
По умолчанию Конечные автоматы...

Задание:

Дан конечный автомат. Проверить принимает ли автомат цепочку ω = 0011. Какие цепочки принимает автомат
М= ({p, q, r}, {0, 1}, δ, q, {r})
а какие отвергает.
Текстовый редактор+функционирующая структура
δ (p, 0) = {q}
δ (p, 1) = {p}
δ (q, 0) = {r}
δ (q, 1) = {p}
δ (r, 0) = {r}
δ (r, 1) = {r}

пояснение:
---------------------------------
Недетерминированный конечный автомат (НКА) - это пятерка M = (Q, T, D(в мойм задании D заменена на δ(сигма)), q0, F), где

Q - конечное множество состояний;
T - конечное множество допустимых входных символов (входной алфавит);
D - функция переходов (отображающая множество QЧ(T {e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;
q0 Q - начальное состояние управляющего устройства;
F Q - множество заключительных состояний.
---------------------------------

Я почитал лекции, различные материалы и вот что понял...
Вот подскажите мне правильно я понял или нет:

Состояний у меня три {p, q, r}, перехода два - по 0 и 1.
Я начинаю идти из q, а прийти должен в r по цепочке 0011.
Глядя на задание получается вот что

(p, 0) = {q} из p при 0 переводит автомат в состояние q
(p, 1) = {p} из p при 1 переводит автомат в состояние p
(q, 0) = {r} из q при 0 переводит автомат в состояние r
(q, 1) = {p} из q при 1 переводит автомат в состояние p
(r, 0) = {r} из r при 0 переводит автомат в состояние r
(r, 1) = {r} из r при 1 переводит автомат в состояние r

а следовательно,
при 0 q->r
при 0 q->r
при 1 r->r
при 1 r->r

получается qrqrrrrr - это ход и в итоге я пришёл по цепочке из q в r.

Я так понял смысл???
Arkuz вне форума Ответить с цитированием
Старый 06.10.2008, 23:36   #2
Arkuz
Форумчанин
 
Аватар для Arkuz
 
Регистрация: 22.09.2007
Сообщений: 538
По умолчанию

ну кто нибудь наведёт на мысль?
Arkuz вне форума Ответить с цитированием
Старый 06.10.2008, 23:36   #3
Arkuz
Форумчанин
 
Аватар для Arkuz
 
Регистрация: 22.09.2007
Сообщений: 538
По умолчанию

ну кто-нибудь!?!?!?!
Arkuz вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме 20000 рублей в месяц

Опции темы



Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS