![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Нормальные алгоритмы Маркова
Определение 2.1. Алгоритмом по Маркову (нормальным алгоритмом) называется ассоциативное исчисление с системой ориентированных подстановок, в котором строго оговорено в какой последовательности следует применять эти подстановки. А именно: а) система допустимых подстановок задается в определенном порядке (номеруется): 1) P1→ Q1; 2) P2→ Q2; …; n) Pn→ Qn; номером i (Pi→ Qi), левая часть которой Pi входит в слово R. Если такой подстановки не найдется, то процесс прекращается. В противном случае берется самое левое вхождение Pi в R и оно заменяется Qi. При этом слово R преобразуется в слово R1. Далее, вместо слова R берется слово R1, и процесс начинается сначала. Так поступают до тех пор, пока процесс не прекратится. А это может произойти в двух случаях: 1) К полученному слову Rk не применима ни одна из данных подстановок; 2) Когда при получении слова Rk применена подстановка с меткой, т.е. заключительная подстановка (ее будем метить справа точкой). При этом считается, что данный алгоритм слово R переработал в слово Rk. Если процесс переработки слова R ни при каком шаге не обрывается, то говорят, что алгоритм к слову R не применим (результат не определен). Итак, любое ассоциативное исчисление с упорядоченной системой ориентированных подстановок, которое снабжено описанной выше «инструкций» относительно очередности применения подстановок, задает нормальный алгоритм. Пример 2.2. Пусть в алфавите A2 ={a, b, c} задана система ориентированных подстановок: 1. cb → cc 2. cca → ab 3. ab → bca 4. ca → Λ Этот алгоритм, будучи применен к слову c abc, никогда не обрывается:
Если же брать слово baaacca, то после нескольких шагов процесс оборвется на слове bb: Два нормальных алгоритма отличаются друг от друга алфавитом и системой ориентированных подстановок или даже только порядком подстановок. Пример 2.3. Пусть в одном и том же алфавите заданы два нормальных алгоритма I1 и I2, отличающиеся друг от друга только порядком подстановок: I1:
I2: 1. bc→ bb 2. ab→ bac 3. ac→ ca 4. aa→ Λ 5. bb→ Λ Этот пример показывает, что в нормальных алгоритмах имеет значение не только сами подстановки, но и их порядок.
|