ВУЗ:
Составители:
процесс обрывается; в противном случае (найдена подстановка), выполняется
подстановка первого вхождения. В результате получаем ***** слово Р
1
. Для
Р
1
выполняется аналогичная процедура и так далее до тех пор, пока на n-м
шаге для слова Р
n
процесс не оборвется. Таким образом, имеем некоторый
алгоритм переработки слов в алфавите А.
Этот алгоритм перерабатывает слова
сввавсвР
=
в слово вва:
ввасвввсваввавсваввавсвсв →→→→ .
Дальнейшие подстановки невозможны. Однако слово
сввсвавсQ =
не может
быть переработано, так как получается бесконечная последовательность
...свавваавссавсвавсвааввсвавссв →→→→→ . Поэтому к слову Q алгоритм не
применим.
В нормальном алгоритме Маркова порядок применения подстановок
следующий. Исходя из произвольного слова Р, все подстановки
просматриваются в естественном порядке. Находится подстановка с левой
частью, входящей в Р. Если таковой нет, то процесс обрывается. В
противном случае берется первая из таких подстановок и выполняется
замена
ее правой части вместо первого вхождения ее левой части в Р, что дает новое
слово Р
1
. Для Р
1
выполняется аналогичная процедура и так далее. Процесс
оканчивается, когда получим слово Р
n
такое, что к нему не применима ни
одна подстановка или когда применяется подстановка, объявленная
последней.
Как видно в отличие от предыдущего алгоритма в нормальном
алгоритме Маркова остановка может наступать в двух случаях.
Если в приведенной выше полутуэвской системе объявим подстановку
сваваа → последней, то ясно, что слово Q будет переработано в слово всва.
Пример 1.3. Пусть задан алфавит
},1{
+
=
А
, подстановка 1) //
+
→+ , 2)
11 →+ ; 3) 11 → и исходное слово 111111111
+
+
.
Применяя подстановки, начиная с первой, получаем последовательно
слова:
1)
111111111 ++ ; 8) 111111111
+
+
;
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
