Учебно-методический комплекс дисциплины для обучающегося «Языки программирования» для специальности 5В010900 Математика
жүктеу/скачать 1.33 Mb.
|
| Пример 1 (вставка и удаление символов)
А={a,b,c,d}. В слове Р требуется заменить первое вхождение подслова bb на ddd и удалить все вхождения символа c. Например: abbcabbca → adddabba Решение. Прежде всего отметим, что в НАМ, в отличие от машины Тьюринга, легко реализуются вставки и удаления символов. Вставка новых символов в слово -это замена некоторого подслова на подслово с бóльшим числом символов; например, с помощью формулы bb→ddd два символа будут заменены на три символа. При этом не надо заботиться о том, чтобы предварительно освободить место для дополнительных символов, в НАМ слово раздвигается автоматически. Удаление же символов - это замена некоторого подслова на подслово с меньшим числом символов; например, удаление символа c реализуется формулой c → (с пустой правой частью). При этом никаких пустых позиций внутри слова не появляется, сжатие слова в НАМ происходит автоматически. С учетом сказанного нашу задачу должен, казалось бы, решать такой НАМ: Однако это не так. Проверим этот НАМ на входном слове abbcabbca (над стрелками указаны номера примененных формул, а в словах слева от стрелок подчеркнуты для наглядности те части, к которым были применены эти формулы): Как видно, заменив первое вхождение bb на ddd, этот НАМ не перешел сразу к удалению символов c, а стал заменять и другие вхождения bb. Почему? Напомним, что на каждом шаге работы НАМ формулы подстановки всегда просматриваются сверху вниз начиная с первой из них. Поэтому, пока применима первая формула, она и будет применяться, блокируя доступ к остальным формулам. Этот означает, что в НАМ важен порядок перечисления формул подстановки. Проверим этот новый алгоритм на том же входном слове: Учтем это и переставим наши две формулы: Итак, НАМ сначала удалил все символы c и только затем заменил первое вхождение bb на ddd. Однако НАМ на этом не остановился и стал заменять остальные вхождения bb. Почему? Дело в том, что, пока применима хотя бы одна формула, НАМ продолжает свою работу. Но нам этого не надо, поэтому мы должны принудительно остановить НАМ после того, как он заменил первое вхождение bb. Вот для этого и нужны заключительные формулы подстановки, после применения которых НАМ останавливается. Следовательно, в нашем алгоритме обычную формулу bb→ddd надо заменить на заключительную формулу bb→ ddd:
Вот теперь наш алгоритм будет работать правильно: Слово, которое получилось после применения заключительной формулы (2), является выходным словом, т.е. результатом применения НАМ к заданному входному слову. Проверим наш НАМ еще и на входном слове, в которое не входит bb: К последнему слову (dab) неприменима ни одна формула, поэтому, согласно определению НАМ, алгоритм останавливается и это слово объявляется выходным. жүктеу/скачать 1.33 Mb. Достарыңызбен бөлісу:
|