Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Автор - А.А. Марков, отдавал предпочтение транскрипции алгори ф м. Нормальные алгорифмы Маркова представляются нормальной схемой подстановок, которая состоит из совокупности подстановок, расположенных в определенном порядке. Подстановки имеют вид: P ® (·) Q (P ® Q – (простая)подстановка, P ® · Q – заключительная подстановка).
Говорят, что строка R входит в строку L, если L имеет вид L1RL2.
Говорят, что подстановка применима к слову, если строка, соответствующая левой части подстановки, входит в слово. Применение заключается в замене в преобразуемом слове левой строки подстановки правой.
Две особые подстановки:
P ® - аннулирующая.
® Q - порождающая.
Механизм работы нормальных алгорифмов:
0) Дано (преобразуемое) слово – цепочка символов фиксированного алфавита и нормальная схема подстановок, содержащая фиксированную последовательность простых и заключительных подстановок.
1) Слово всегда просматривается слева направо.
Схема подстановок просматривается всегда начиная с первой подстановки и, если подстановку можно применить, то она применяется к самому левому вхождению этой строки в преобразуемое слово.
2) Работа алгоритма заканчивается тогда, когда ни одна из подстановок не применима, либо.использована заключительная подстановка.
Примеры.
Дата публикования: 2014-11-03; Прочитано: 286 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!