Разработка программ для алгоритмов Маркова. Факультет компьютеризированных систем и информационных технологий Кафедра информатики и программной инженерии
 Скачать 54.84 Kb.
|
|
государственное образовательное учреждение высшего профессионального образования луганской народной республики «луганский национальный университет имени владимира даля» Факультет компьютеризированных систем и информационных технологий Кафедра информатики и программной инженерии Лабораторная работа Выполнил: студент 2 курса группы ИT-691 Шамин Иван Проверил: Луганск, 2020 г. Лабораторная №3 Разработка программ для алгоритмов Маркова Цель работы: развить аналитическое и логическое мышление учащихся, математическую интуицию посредством разработки алгоритмов задач для логических машин. Задание Текст задания: Составить нормальный алгоритм, преобразующий исходную строку в алфавите A = {a, b, c} в строку, в которой буквы расположены в алфавитном порядке. Вставить скриншот состояния ленты до выполнения алгоритма. До изменения  После выполнения 
Контрольные вопросы. 1. Что такое алгоритм Маркова. Нормальный алгоритм задает метод преобразования строк с помощью системы подстановок. Каждая подстановка состоит из слова-образца и слова-замены, разделенных цепочкой символов «->». На каждом шаге замены подстановки просматриваются по порядку сверху вниз, и выполняется первая из них, которая подошла: первое найденное слово-образец рабочей строки заменяется на слово-замену 2. Система подстановок алгоритма Маркова Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики 3. Правила выполнения алгоритмов Маркова Если левая часть левая часть некоторого слова входит в данное слово, то происходит замена. Завершение преобразования происходит в двух случаях: 1) Если не одно из правил не может быть применено к текущему слову. 2) Если существует терминальное правило. Левая часть подстановки может быть пустой: правило подстановки у пустой левой части лова считается применимой к любому слову, его действие состоит в том, что к началу слова добавляется правая часть этого правила. Если правая часть пустая, тогда это соответствует удалению соответствующих символов и слов. 4. Варианты окончания выполнения программы. Корректная остановка, бесконечное зацикливание. |