Cтраница 2
Рассмотрим весьма важный частный случай дедуктивной грамматики, порождающей язык слов. Марковской подстановкой в алфавите A U С называется операция, обозначаемая P: - Q, где Р и Q - слова в Л U С, заключающаяся в том, что в преобразуемом слове находят первое ( если считать от начала) вхождение слова Р и заменяют последнее словом Q; то, что получится, является результатом выполнения операции. В тех случаях, когда Р не входит в преобразуемое слово, операцию будем считать неприменимой к этому слову. Будем считать, что слово Р является непустым. [16]
Хомским, не являются марковскими подстановками ( см. § 3 гл. Объектом преобразования для таких подстановок могут быть только слова, но применение подстановки допускает произвол. Если преобразуемое слово имеет несколько вхождений слова Р, то подстановка допускает замену любого из этих вхождений правой частью формулы. [17]
Значит, если слово пусто, то сдвинуться с приказа 1 не удается. Это значит, что наш натуральный алгориТхМ к пустому слову неприменим. Приказ 2 предписывает найти начало преобразуемого слова и перейти к приказу 3, приказ 3 - проверить, является ли рассматриваемая буква концом слова, и если да, перейти к приказу 100, которого нет. Это значит, что процесс окончен. Если же рассматриваемая буква еще не конец слова, то по приказу 4 нужно продвинуться вправо и снова вернуться к приказу 3 для проверки, не найден ли еще конец. [18]
Рассмотрим весьма важный частный случай дедуктивной грамматики, порождающей язык слов. Марковской подстановкой в алфавите A U С называется операция, обозначаемая P: - Q, где Р и Q - слова в Л U С, заключающаяся в том, что в преобразуемом слове находят первое ( если считать от начала) вхождение слова Р и заменяют последнее словом Q; то, что получится, является результатом выполнения операции. В тех случаях, когда Р не входит в преобразуемое слово, операцию будем считать неприменимой к этому слову. Будем считать, что слово Р является непустым. [19]
Двигаясь по столбцу формул, ищут первую формулу, левая часть которой входит в преобразуемое слово. Если такой формулы не найдется, процесс окончен. Если же она найдется, то выполняют марковскую подстановку, соответствующую данной формуле, изменяя преобразуемое слово. [20]
Как видно, в том и другом случае операция в машинной программе реализуется с помощью цикла и потому операции будут выполняться медленно. Между тем во многих задачах операции удаления и вставки символов, а также другие операции, приводящие к изменению длины строки, являются наиболее частыми. Например, применение нормального алгоритма к входному слову как раз в основном и сводится к применению формул подстановок, когда в преобразуемом слове удаляется ( первое по порядку) вхождение левой части формулы и вместо нее вставляется правая часть формулы подстановки, причем длины левой и правой частей, вообще говоря, различны. [21]
Предположим теперь для определенности, что алфавит А - это алфавит латинских строчных букв. Представим себе, что задано некоторое слово в А, и мы хотим все имеющиеся в нем буквы а заменить на i, а все имеющиеся буквы i заменить на а. Ясно, что если преобразуемое слово в А является пустым, алгоритм к нему должен быть неприменимым. [22]