Аннотация:
В статье описан маленький, но всё равно интересный кусочек теории вычислений. Предназначение статьи – послужить наживкой, заглотив которую, читатели уже сами продолжат изучение этой теории.
СХ>Авторы: СХ> Сергей Холодилов
СХ>Аннотация: СХ>В статье описан маленький, но всё равно интересный кусочек теории вычислений. Предназначение статьи – послужить наживкой, заглотив которую, читатели уже сами продолжат изучение этой теории.
"F – множество допускающих состояний, является подмножеством Q."
К тому моменту, как текст на сайте окончился. слово "допускающий" не стало понятным. ... а говорили, что для чайников!
Здравствуйте, Аноним, Вы писали:
А>"F – множество допускающих состояний, является подмножеством Q."
А>К тому моменту, как текст на сайте окончился. слово "допускающий" не стало понятным. ... а говорили, что для чайников!
Вот этот кусок — понятен?
И функционирующее следующим образом:
* Автомат начинает работу в состоянии q0.
* Если автомат находится в состоянии qi, а на вход поступает символ b, то автомат переходит в состояние δ(qi, b).
Тогда описание, что такое "допускающее состояние" — тут:
Работа ДКА заключается в распознавании цепочек символов, принадлежащих множеству Σ. Если, обработав цепочку, автомат оказался в допускающем состоянии, то цепочка считается допустимой, если нет, то нет. Таким образом, ДКА задаёт некоторый язык – множество допускаемых им цепочек, алфавит этого языка – множество Σ.
В статье действительно нет примера работы ДКА, я надеялся, что представление о ДКА у читателей уже есть. Так что если не ясно, задавай уточняющие вопросы — отвечу.
Здравствуйте, SergH, Вы писали:
SH>В статье действительно нет примера работы ДКА, я надеялся, что представление о ДКА у читателей уже есть. Так что если не ясно, задавай уточняющие вопросы — отвечу.
Ну вот пример. Берём автомат из примера, натравливаем его на цепочку 1110101. Получаем последовательность состояний:
К концу цепочки автомат находится в состоянии q0. Оно не допускающее. Значит, автомат не допускает эту цепочку, такая цепочка не принадлежит языку, заданному этим автоматом.
К концу цепочки автомат находится в состоянии q1. Оно допускающее. Значит, автомат допускает эту цепочку, такая цепочка принадлежит языку, заданному этим автоматом.
Несложно заметить, что этот автомат допускает любые цепочки из 1-0, заканчивающиеся на 0. Т.е., в терминах регулярных выражений, тот же язык выглядит так: (0 + 1)*0
Спасибо за статью, кратко но познавательно написано
Вот только форматирование кода съехало — for, foreach и break начинаются почему-то с середины строки (Firefox 2.0.0.7).
Здравствуйте, Left2, Вы писали:
L>Вот только форматирование кода съехало — for, foreach и break начинаются почему-то с середины строки (Firefox 2.0.0.7).
> В замечательной программе JFLAP, скриншоты из которой используются в качестве рисунков, ε-переходы почему-то обозначаются символом λ, но я нашёл в себе силы поправить картинки.
Константин Думан написал по почте:
Хотел сообщить вам, что в новой версии (а может быть это было и в прошлых) появилась возможность настраивать свободные переходы. В настройках выбираете либо епсилон, либо лямбду. По умолчанию выставлено второе
> Очень рекомендую, правда, вряд ли вы её найдёте в магазинах, разве что на русском выпустят третье издание.
Кстати, ещё раз выпустили второе, вроде с какими-то исправлениями.
