Теоретическая часть. Любое непустое множество символов будем называть алфавитом

Любое непустое множество символов будем называть алфавитом. Буквы – это символы алфавита. Любая конечная последовательность букв алфавита называется словом. Пустое слово – это пустая последовательность букв.

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

Большинство алгоритмов можно разбить на некоторые простейшие шаги. Пусть P и Q – слова (возможно - пустые) в алфавите A. Простая подстановка P Q меняет слово P на слово Q. После этого работа алгоритма продолжается. Заключительная подстановка P Q также меняет слово P на слово Q, но после этого работа алгоритма заканчивается.

Схема алгоритма состоит из конечного списка формул подстановки. Говорят, что слово T входит в слово S, если существуют такие (возможно, пустые) слова V и W, что S=VTW.

Работа нормального алгоритма Маркова заключается в применении схемы алгоритма к слову в алфавите A. При завершении работы алгоритма за конечное число шагов говорят о применимости алгоритма к слову.