Нормальные алгоритмы Маркова

Нормальный алгоритм Маркова представляет собой систему подстановок

, (4.10)

где - слова из символов входного алфавита

- оператор подстановки, при этом :

-простая подстановка

- заключительная подстановка.

Слово z считается включенным в слово у, если у может быть представлено как:

, (4.11)

где - любые символы входного алфавита.

 

Работа нормального алгоритма Маркова:

Исходное слово просматривается слева направо с целью выявления вхождения первого правила подстановки. Как только находится первое вхождение первого правила подстановки, оно заменяется по этому правилу и исходное слово снова просматривается с первого символа по первому правилу подстановки.

После того, как первое правило больше не встречается в данном слове, аналогично применяется второе правило подстановки.

Работа алгоритма заканчивается тогда, когда ни одна из подстановок не применима, либо.использована заключительная подстановка.

 

ПРИМЕР

Построить нормальный алгоритм Маркова, стирающий последовательность единиц.

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

1.

2.

Первая подстановка стирает все единицы до последней. Вторая (заключительная) подстановка заменяет последнюю единицу пробелом .

Тезис А. Черча. Если функция выполнима, то она может быть представлена в виде нормального алгоритма Маркова.

 

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

 

 

ТЕОРИЯ АВТОМАТОВ

 

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

В данном разделе рассматриваются абстрактные автоматы, т.е. некоторая математическая модель. Вопросы практической реализации не рассматриваются. В связи с этим при построении автоматов будем иметь в виду, что:

1. Автомат функционирует в абстрактном времени.

2. Все переходы происходят мгновенно.

Автомат представляет собой кортеж 6 –го порядка:

, (5.1)

где – множество входных сигналов (входной алфавит),

– множество выходных сигналов (выходной алфавит),

– множество внутренних состояний,

– функция перехода,

– функция выхода,

- начальное состояние автомата.