Нормальные алгоритмы Маркова. Урок 1. Markov Algorithms. Lesson 1.

• Понятие нормальных алгоритмов Маркова введено в 1947 году Андреем Андреевичем Марковым.  

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

• Слово — это произвольная последовательность символов из некоторого алфавита.  

• Нормальный алгоритм Маркова состоит из правил подстановки.  

• Каждое правило подстановки состоит из левой части и правой части.  

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

• Пример алгоритма содержит два правила подстановки.  

• Первое правило заменяет буквы "а" на "а б а".  

• Второе правило заменяет буквы "б" на "б а б".  

• Применение алгоритма к слову "а а бб а а" приводит к замене букв и получению слова "а-б-а б-а-б-а".  

• Преобразование слова по правилам подстановки — это последовательность однотипных шагов.  

• На каждом шаге просматриваются правила и заменяются вхождения левой части на правую часть.  

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

• Преобразование завершается, если ни одно из правил неприменимо.  

• Терминальные правила завершают процесс преобразования.  

• Терминальные правила обозначаются стрелкой с вертикальной чертой.  

• Если левая часть правила входит в слово более одного раза, заменяется только самое левое вхождение.  

• После каждого применения правила просмотр начинается сначала.  

• Пустая левая часть правила добавляет правую часть к началу слова.  

• Пустая правая часть удаляет последовательность символов, совпадающих с левой частью.  

• В примере сделано три шага преобразования.  

• Первое правило применяется к слову "а а".  

• Второе правило применяется к слову, полученному после первого шага.  

• Третье правило применяется к слову, полученному после второго шага.  

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