Cтраница 1
Преобразуемое слово состоит из элементов. Если найдется такой момент времени, когда два идеальные элемента а, 6 сразу находятся в слове, то в течение всего совместного существования относительный порядок их будет оставаться неизменным. [1]
Проверить, поддается ли преобразуемое слово i-той ф-ле. [2]
Проверить, поддается ли преобразуемое слово г-той ф-ле. [3]
Если в какой-нибудь момент времени в преобразуемом слове одновременно находятся три последовательные элемента из цепочки, то средний можно выбросить, - в результате получится укороченная монотонная цепочка с тем же началом и концом. [4]
Если удалось применить какую-то формулу подстановки, найдя в преобразуемом слове левую часть формулы и заменив ее на правую часть, то всегда на следующем такте возвращаются к самому началу нормального алгоритма и снова ищут вхождение левой части первой формулы в измененное слово. Если же какую-то формулу не удалось применить, то происходит попытка применить следующую за ней формулу. [5]
Каждая пара представляет собой формулу подстановки для замены подслов в преобразуемом слове. [6]
Двигаясь по столбцу формул, ищут первую формулу, левая часть которой входит в преобразуемое слово. Если такой формулы не найдется, процесс окончен. Если же она найдется, то выполняют марковскую подстановку, соответствующую данной формуле, изменяя преобразуемое слово. [7]
По определению, вхождения пустого сло ва имеются слева и справа от каждой буквы в преобразуемом слове. Первое из них предшествует первой букве слова. [8]
В схемах на рис. 1.5.1, в, 1.5.2, в, 1.5.3, а количество регистров зависит от разрядности преобразуемого слова. Процесс записи, считывания и преобразования остается таким же, как было описано выше. [9]
Левую и правую части формулы, которая применяется в данный момент, будем хранить в специальных рабочих массивах лев и прав в виде цепочек, чтобы удобно было сопоставлять их с цепочкой преобразуемого слова в массиве слово. При выделении из массива алг очередной формулы используем процедуру ЧАСТЬ ФОРМУЛЫ ( Х), которая при подстановке вместо X фактического параметра лев или прав будет выделять соответствующую левую или правую часть формула и формировать из нее цепочку символов в массиве лев или прав. [10]
Если обратиться теперь к конкретизации вывода, то для осуществления преобразования через раз нам еще предстоит разработать какой-то аппарат; кроме того, для вывода слова ( особенно о конца) нужно знать количество символов в преобразуемом слове, и об этом нужно позаботиться еще при вводе. [11]
В заданном слове каждая пара друг другу соответствующих скобок заменяется оболочкой. Затем буквы в А или оболочки, перед которыми в преобразуемом слове стоят имена ветвей связей, фиксируются соответствующими ветвями соответствующих связей. Затем отбрасывают все имена связей и все связи следования букв, которые присутствовали в преобразованном слове. [12]
В 1954 г. советский математик А. А. Марков предложил алгоритмическую схему, в которой, как и в машине Тьюринга, преобразуются слова, но на основе других принципов. В алгоритмической схеме Маркова нет понятия ленты и подразумевается непосредственный доступ к различным частям преобразуемого слова. [13]
В левых и правых частях формул подстановок могут содержаться пустые слова. Для записи нормальных алгоритмов не требуется специального обозначения пустого слова, так как в этой конструкции нет ячеек, не зафиксирован носитель информации, а преобразуемое слово свободно раздвигается и сужается. [14]
Рассмотрим весьма важный частный случай дедуктивной грамматики, порождающей язык слов. Марковской подстановкой в алфавите Ли С называется операция, обозначаемая P: Q, где Р и Q-слова в Л и С, заключающаяся в том, что в преобразуемом слове находят первое ( если считать от начала) вхождение слова Р и заменяют последнее словом Q; то, что получится, является результатом выполнения операции. [15]