русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Правила выполнения НАМ


Дата добавления: 2013-12-23; просмотров: 2487; Нарушение авторских прав


Определение НАМ

Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки:

(14.1)

В этих формулах могут использоваться два вида стрелок: обычная стрелка () и стрелка «с хвостиком» (). Формула с обычной стрелкой называется обычной формулой, а формула со стрелкой «с хвостиком» – заключительной формулой. Разница между ними объясняется чуть ниже.

Записать алгоритм в виде НАМ – значит предъявить такой набор формул.

 

Прежде всего, задается некоторое входное слово Р. Где именно оно записано – не важно, в НАМ этот вопрос не оговаривается.

Работа НАМ сводится к выполнению последовательности шагов. На каждом шаге входящие в НАМ формулы подстановки просматриваются сверху вниз и выбирается первая из формул, применимых к входному слову Р, т. е. самая верхняя из тех, левая часть которых входит в Р. Далее выполняется подстановка согласно найденной формуле. Получается новое слово Р′.

На следующем шаге это слово Р′ берется за исходное и к нему применяется та же самая процедура, т. е. формулы снова просматриваются сверху вниз начиная с самой верхней и ищется первая формула, применимая к слову Р′, после чего выполняется соответствующая подстановка и получается новое слово Р′′. И так далее (рисунок 14.5).

Рисунок 14.5 – Иллюстрация правила выполнения НАМ

 

Следует обратить особое внимание на тот факт, что на каждом шаге формулы в НАМ всегда просматриваются начиная с самой первой.

Необходимые уточнения:

1. Если на очередном шаге была применена обычная формула (αβ), то работа НАМ продолжается.

2. Если же на очередном шаге была применена заключительная формула (αβ), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т. е. результат применения НАМ к входному слову.



Как видно, разница между обычной и заключительной формулами подстановки проявляется лишь в том, что после применения обычной формулы работа НАМ продолжается, а после заключительной формулы – прекращается.

3. Если на очередном шаге к текущему слову неприменима ни одна формула, то и в этом случае работа НАМ прекращается, а выходным словом считается текущее слово.

Таким образом, НАМ останавливается по двум причинам: либо была применена заключительная формула, либо ни одна из формул не подошла. То и другое считается «хорошим» окончанием работы НАМ. В обоих случаях говорят, что НАМ применим к входному слову.

Однако может случиться и так, что НАМ никогда не остановится; это происходит, когда на каждом шаге есть применимая формула и эта формула обычная. Тогда говорят, что НАМ неприменим к входному слову. В этом случае ни о каком результате нет и речи.

 

14.4 Пример составления НАМ

 

Рассмотрим пример, в который демонстрируются типичные приёмы составления НАМ.

Как и в случае машины Тьюринга, для сокращения формулировки задачи будем использовать следующие соглашения:

– буквой Р будем обозначать входное слово;

– буквой А будем обозначать алфавит входного слова, т. е. набор тех символов, которые и только которые могут входить во входное слово Р (но в процессе выполнения НАМ в обрабатываемых словах могут появляться и другие символы).

Кроме того, в примере будем справа от формул подстановки указывать их номера. Эти номера не входят в формулы, а нужны для ссылок на формулы при показе пошагового выполнения НАМ.

 

Пример 1 (вставка и удаление символов).

Дано А={a,b,c,d}. В слове Р требуется заменить первое вхождение подслова bb на ddd и удалить все вхождения символа c.

Например: abbcabbca adddabba



<== предыдущая лекция | следующая лекция ==>
Краткое описание нормальных алгоритмов Маркова | Решение.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.