Буквы, абстрактные алфавиты

Буквы, абстрактные алфавиты

Любой алгоритм представляет собой информационную модель некоторого процесса, записанного с помощью  системы команд исполнителя. Ранее  было показано, что  информационные модели – это модели из букв. Буква  всегда была основой отображения  знаний. А в 17 в. Франсуа Виет предложил использовать буквы для описания различных значений, тем самым ‘а’ перестало быть просто символом для обозначения звука.

Буква как понятие, а не как символ характеризуется следующими свойствами:

самотождественность: а=а;

дискретность: а всегда отличается от в;

финитность: буква всегда принадлежит конечному множеству – алфавиту;

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

Из этих свойств вытекает следующие определения:

Любая конечная система попарно  различимых знаков называется абстрактным  алфавитом (или просто алфавитом), а  все его элементы называются буквами.

Любая конечная последовательность букв алфавита называется словом. Количество букв в слове называется его длиной. Слово, не содержащее ни одной буквы, называется пустым.

Алфавитным операторомназывается функция, сопоставляющая словам в некотором алфавите слова в том же или другом алфавите.

Над словами алфавита, независимо от того, каким объектам эти слова  соответствуют, выполняются разрешимые операции

Вхождение. Слово Pвходит в слово Q, если Q=P1PP2, где Q,, P1,P,P2– слова

одного алфавита.

Подстановка– это замена в некотором словеRвсех вхождений слова PсловомQ. И наоборот. Обозначается P↔Q

Ориентированная подстановка– это замена вхождений слова PсловомQв некотором слове R. Обозначены P→Q, где P– левая, а Q– правая часть постановки.

Упорядоченной системой подстановокназывается последовательность подстановок, применяемая в соответствии со следующими правилами:

Первая по порядку пригодная  подстановка применяется к первому  вхождению ее левой части в  исходное слово;

Полученное по правилу 1 слово  становится исходным и процедура  повторяется;

Процедура останавливается, когда будет получено слово, к  которому ни одна из подстановок не применима