Содержание к диссертации
Введение
1.1 Обзор содержания работы 5
1.2 Основы модельно-ориентированного подхода к разработке программного обеспечения 8
1.2.1 Проблемы и задачи, которые решает MDA 8
1.2.2 Процесс разработки программного обеспечения по методике MDA 9
1.2.3 Преимущества использования методики MDA 12
1.2.4 Роль автоматизированной трансформации моделей в MDA 12
1.3 Задача автоматизированной трансформации моделей 14
1.3.1 Описание трансформации и инструмент трансформации 14
1.3.2 Требования к средству трансформации для его использования в MDA 16
Глава 2. Обзор основных стандартов и работ, относящихся к трансформации моделей. 19
2.1 Стандарты, связанные с моделированием на UML 19
2.1.1 Язык моделирования UML 19
2.1.2 Метамоделирование и стандарт MOF 23
2.1.3 Язык объектных ограничений Object Constraint Language 26
2.2 Основные подходы к трансформации моделей 33
2.2.1 Трансформация, встроенная в инструмент 33
2.2.2 Использование языков общего назначения 34
2.2.3 Использование механизмов трансформации из других областей 35
2.2.4 Использование технологий работы с XML 35
2.2.5 Трансформация с помощью UML как универсального языка 36
2.2.6 Использование специализированного языка трансформации 37
2.3 Обзор работ в области трансформации моделей 37
2.3.1 MOF: запросы, представления, трансформации 37
2.3.2 Трансформация: недостающее звено MDA 40
2.3.3 Классификация подходов к трансформации моделей 41
2.3.4 Декларативная трансформация объектно-ориентированных моделей 42
2.3.5 Спецификация трансформаций модели на уровне метамодели 44
2.3.6 Трансляция моделей 45
2.3.7 Сравнение двух подходов к трансформации моделей 46
Глава 3. Язык трансформации моделей 49
3.1. Представление моделей и метамоделей 49
3.2. Основы языка трансформации 53
3.2.1 Язык запросов к модели 53
3.2.2 Правило трансформации 58
3.2.3 Блок и описание трансформации 61
3.2.4 Выполнение трансформации 63
3.2.5 Генерация и трансформация нескольких моделей 66
3.3. Трансформационные связи 68
3.4. Полнота языка трансформации 71
3.4.1 Математическая полнота языка трансформации 72
3.4.2 Алгоритмическая полнота языка трансформации 77
3.5. Расширенные возможности языка 86
3.5.1 Уточнение правил 86
3.5.2 Несущественные и симметричные переменные выборки 88
3.5.3 Оператор печати 90
3.5.4 Оператор завершения блока и трансформации 91
3.4.1 Условный оператор 92
3.4.2 Доступ к текущему экземпляру трансформационной связи 93
3.4.3 Нумерация применения правил 94
Глава 4. Практическая реализация трансформаций для различных платформ, особенности инструмента трансформации 96
4.1. Пример перехода от платформо-иезависимой модели классов UML к модели,
предназначенной для реализации на платформе CORBA 96
4.1.1 Описание трансформации для перехода от UML-модели классов к модели, предназначенной для реализации на платформе CORBA 98
4.1.2 Наследование реализации в CORBA-системе и необходимая для этого трансформация моделей 104
4.2. Преобразование UML-модели классов в реляционную модель 107
4.3. Использование правил трансформации для контроля инвариантов мстамодсли 112
4.4. Особенности практической реализации инструмента трансформации 117
4.4.1 Вычисление запросов к модели и секция выборки 118
4.4.2 Применение правила и секция генерации 122
4.4.3 Ввод описания трансформации 122
4.4.4 Ввод/вывод моделей 123
Глава 5. Заключение 125
5.1. Результаты работы 125
5.2. Перспективы дальнейшей работы 126
Список литературы
- Процесс разработки программного обеспечения по методике MDA
- Метамоделирование и стандарт MOF
- Блок и описание трансформации
- Наследование реализации в CORBA-системе и необходимая для этого трансформация моделей
Введение к работе
Модельно-ориентированный подход к разработке программного обеспечения (MDA) - это новая методика разработки программ, развиваемая консорциумом OMG начиная с 2000-го года. Этот подход имеет ряд преимуществ по сравнению с используемыми на данный момент. В его основу положен процесс создания пары программных моделей разрабатываемой системы, одна из которых представляет структуру и поведение системы с точки зрения пользователя, а другая - детали реализации этой системы с использованием какого-либо вида программного обеспечения промежуточного уровня [1]. Далее в работе подход MDA, его особенности и преимущества будут рассмотрены подробнее.
Но при всех достоинствах такого подхода необходимость создания двух моделей вместо одной при разработке программной системы, основанной на MDA, может существенно замедлить процесс разработки программного обеспечения. Этот недостаток уменьшает эффективность и область применимости подхода MDA. Однако разработчиками подхода было замечено, что после создания одной из пары моделей, используемых в MDA, можно существенно автоматизировать процесс получения другой модели. Для этого необходимо задать набор преобразований, который позволяет из исходной модели, отражающей одно представление системы, получить модель, соответствующую другому представлению. Каждое представление при этом отражает набор понятий и элементов, характерных для определённой технологической платформы или программного обеспечения промежуточного уровня. Если преобразование моделей задано на некотором формальном языке, и существует алгоритм автоматического выполнения таких преобразований, оно будет называться описанием трансформации моделей (model transformation). Язык описания трансформации, алгоритм автоматического выполнения трансформаций и программный инструмент, их выполняющий, будем называть средством трансформации моделей.
Целью данной работы является разработка средства описания трансформации программных моделей, пригодного для автоматизации преобразования моделей в технологии MDA.
Для достижения этой цели требуется решить следующие задачи: - анализ критериев оценки эффективности средств трансформации моделей с точки зрения их использования в MDA;
- разработка языка трансформации моделей, соответствующего сформулированным критериям;
- создание инструмента трансформации, позволяющего автоматически выполнять трансформации, заданные с помощью разработанного языка.
Актуальность работы заключается в том, что без использования автоматического преобразования моделей подход MDA не может реализовать весь свой потенциал. В то же время существующие средства и языки общего назначения, с помощью которых можно было бы описать преобразования моделей, оказываются недостаточно эффективными в контексте применения в MDA, что обуславливает необходимость создания нового специализированного средства трансформации с учётом потребностей этой технологии.
Во введении проводится обзор модельно-ориентированного подхода к разработке программных систем (MDA), рассматриваются его особенности и преимущества по сравнению с традиционными подходами. Описываются основные этапы разработки программной системы по методике MDA и основные понятия этой методики. В частности, вводятся понятия платформо-независимой и платформо-зависимой моделей, описываются различия между ними и преимущества, получаемые от описания программной системы с помощью двух моделей разного уровня абстракции.
Далее описывается роль трансформации моделей в технологии MDA и ставится задача автоматизации перехода от платформо-независимой к платформо-зависимой модели. Вводятся понятия трансформации как перехода от одной модели к другой по заданному описанию, языка описания трансформации и инструмента, автоматически выполняющего трансформацию моделей, заданную с помощью формального языка. Производится постановка задачи автоматизированной трансформации моделей, рассматриваются характеристики, которыми должен обладать язык трансформации для его успешного использования в задачах преобразования моделей, характерных для технологии MDA.
Во второй главе данной работы рассматриваются основные стандарты, имеющие отношение к трансформации моделей. Также исследуется возможность применения для описания трансформации моделей ряда существующих языков и методов из других областей программирования. Анализируются недостатки каждого из этих методов применительно к задаче трансформации моделей в контексте MDA. Делается вывод о том, что необходимо создание нового языка, специализированного для описания трансформаций UML-моделей, оперирующего в терминах данной предметной области и учитывающего специфику применения.
Далее во второй главе проводится обзор работ в области трансформации моделей. Особое внимание уделено работам, в которых разработчики подхода MDA сформулировали требования, которым, по их мнению, должно удовлетворять средство трансформации моделей для его эффективного использования в MDA. Помимо этого, рассматривается ряд работ, предлагающих общие подходы к трансформации моделей.
В третьей главе работы описывается предложенный автором язык трансформации моделей. На основе рассмотренных ранее работ делается вывод о том, что язык должен быть основан на концепции правил трансформации. Правило трансформации - это конструкция языка, задающая соответствие между фрагментом исходной модели и желаемым результатом преобразования этого фрагмента. Описание трансформации, задаваемое с помощью набора таких правил, по структуре наиболее близко к описаниям преобразований моделей на естественном языке и потому удобнее в использовании и легче для понимания по сравнению с другими методами (такими, как императивное описание трансформации в виде последовательности действий).
При описании правила трансформации предлагается задавать область применимости правила в виде шаблона, представляющего собой набор элементов метамодели и условий, которые должны быть выполнены, чтобы правило считалось применимым. В работе предлагаются синтаксические конструкции языка, основанные на синтаксисе языка объектных ограничений OCL, которые позволяют задавать подобные шаблоны.
Каждому используемому в шаблоне элементу метамодели ставится в соответствие уникальное имя переменной, что позволяет легко задавать условия, уточняющие шаблон, а также использовать эти переменные для описания результата применения правила. Результат применения правила к фрагменту модели, подходящему под шаблон, предлагается описывать императивно, в виде набора операторов изменения модели, применяемых к объявленным в шаблоне переменным.
Описание трансформации на предложенном языке представляет собой набор правил трансформации, сгруппированных в блоки трансформации. В работе предложен простой алгоритм, позволяющий автоматически выполнять заданные таким образом описания. Процесс трансформации заключается в поиске применимого правила и фрагмента модели, подходящего под шаблон, и модификации выбранного фрагмента модели в соответствии с заданным в правиле набором операций. После этого поиск применимого к изменённой модели правила начинается заново.
Предложенный язык трансформации решает задачу преобразования одной модели, однако в работе описано расширение этого языка, позволяющее задавать трансформации нескольких моделей и генерацию новой модели по исходной.
В работе предложен оригинальный механизм трансформационных связей -структур данных, сохраняющих информацию о применении правил. Это позволяет не только отслеживать соответствие между исходными и порождёнными элементами модели после трансформации, что является одним из требований технологии MDA, но и использовать результат применения одних правил в других правилах, тем самым создавая зависимости между правилами и иерархии правил. Эти структуры объединяются в специальную модель связей, имеющую структуру, аналогичную структуре трансформируемых моделей. Благодаря такому сходству структур оказывается возможным использовать общие принципы и конструкции языка для работы с обычными моделями и моделью связей, что упрощает синтаксис языка и облегчает его понимание.
Далее в работе проводится исследование класса преобразований моделей, который можно описать с помощью предложенного языка. Доказывается, что можно формально описать любые преобразования, заданные с помощью однозначного отображения конечных множеств моделей. Также доказывается, что можно описать любые преобразования, заданные в виде формальных алгоритмов (для формализации понятия алгоритма используется концепция машины Тьюринга).
В четвертой главе работы на примерах показана возможность и удобство использования разработанного языка для описания трансформаций. В качестве примеров выбраны типичные задачи перехода от платформо-независимой к платформо-зависимой модели, решение которых используется в технологии MDA. Также демонстрируется возможность использования разработанного языка для контроля правильности трансформаций и обнаружения ошибок.
Кроме того, в четвертой главе работы рассмотрена структура прототипа инструмента трансформации, созданного в рамках данной работы и предназначенного для автоматического выполнения заданных на предложенном языке трансформаций моделей. Обсуждаются основные компоненты этого инструмента, принципы и особенности их функционирования, а также практические задачи, возникшие в процессе реализации инструмента, и способы их решения.
В заключении диссертации подводятся итоги работы и анализируются полученные результаты. Рассматриваются перспективы дальнейшего развития разработанного средства трансформации моделей. Ставится ряд задач, связанных с проведённой работой в области трансформации моделей и требующих дальнейшего изучения.
Процесс разработки программного обеспечения по методике MDA
При разработке программного обеспечения по технологии MDA используется набор стадий, сходный с другими распространёнными подходами к разработке, такими как, например, методика Rational Unified Process (RUP). В этом смысле MDA является эволюционным развитием существующих методик. Новизна подхода заключается в результатах стадий анализа и проектирования, а именно в представлении системы с помощью двух моделей, создающихся на разных стадиях.
В основе MDA лежат понятия платформо-независимой и платформо-зависимой моделей (platform-independent и platform-specific models, PIM и PSM) [3]. В процессе разработки системы сначала создаётся Р1М - программная модель, содержащая бизнес-логику системы без конкретных деталей её реализации, относящихся к какой либо технологической платформе. Принципиальным является именно тот факт, что на этапе создания этой модели не принимается никаких решений по поводу её реализации, разрабатываемый программный продукт не привязывается к технологиям. На этом этапе в модель закладывается бизнес-логика, сценарии использования, функциональные требования и другая информация о взаимодействии системы с пользователем и о желаемом поведении системы. При использовании MDA рекомендуется доводить платформо-независимую модель по достаточно высокой степени детализации, вплоть до использования высокоуровневого платформо-независимого языка программирования для описания функциональности и создания исполняемой модели. Однако следует отличать детали функциональности, описывающие поведение системы с точки зрения пользователя, от деталей её практической реализации: последние не должны присутствовать в платформо-независимой модели.
Заметим, что даже если PIM доводится до стадии детальной исполняемой модели, её вряд ли можно использовать на практике как финальный программный продукт. Такая модель может быть крайне неэффективной при выполнении, не удовлетворять некоторым функциональным требованиям, не полностью реализовывать функциональность системы и даже требовать участия человека в процессе исполнения. Только после привязывания к конкретной платформе можно получить программный код промышленного качества. Но хотя исполнение РІМ-модели и не применимо для решения практических задач, оно необычайно важно для тестирования и отладки. Фактически, появляется возможность получить первый прототип системы ещё до начала стадии кодирования, когда сравнительно легко вносить даже существенные изменения в систему, в том числе производить изменения требований и технического задания.
Итак, результатом первого этапа разработки по технологии MDA является платформо-независимая модель, заданная с помощью некоторого формального языка моделирования. Завершённая платформо-независимая модель содержит полное описание системы, но свободна от деталей, относящихся к реализации и используемым технологиям.
После того, как Р1М в достаточной степени детализирована, выполняется переход к платформо-зависимой модели. Эта модель описывает уже не только функциональность системы, но и её реализацию с использованием конкретной (выбранной для данного проекта) технологической платформы. Происходит дальнейшая детализация модели и добавление элементов и конструкций, специфичных для выбранной технологии реализации. После того, как модель достаточно разработана, выполняется генерация кода по модели, затем производится доработка этого кода и его компиляция, так же, как и в традиционных методиках разработки программного обеспечения.
Разумеется, реально процесс разработки не столь линеен. Для сложного проекта практически невозможно сразу создать платформо-независимую модель, которая бы не потребовала изменений на более поздних стадиях. В процессе разработки платформо-зависимой модели и даже при написании кода может возникнуть необходимость в изменении любой из моделей. Это вполне допускается технологическим процессом MDA, однако необходимо следить, чтобы сохранялось соответствие между моделями: изменения в одной должны быть отображены на другие. Таким образом, при использовании технологии MDA одновременно разрабатываются и изменяются сразу три модели (Р1М, PSM и код), представляющие разрабатываемую систему с разных точек зрения и с различными уровнями детализации.
В принципе, идея, положенная в основу MDA, не зависит от инструментов и языка моделирования. Но поскольку эта технология создана консорциумом OMG, который занимается, помимо прочего, развитием языка моделирования UML (Unified Modeling Language) [4,5], предполагается, что именно этот язык будет использоваться для описания моделей при разработке программного обеспечения по технологии MDA. Язык UML в настоящее время очень популярен и повсеместно используется для моделирования программных систем, так что ориентация методики MDA именно на этот язык вполне оправдана. В последних версиях стандарта UML появились дополнения, которые делают этот язык более удобным для такого использования: язык действий (action semantics) [6] позволяет описывать функциональность системы на платформо-независимом уровне, а профили (UML Profiles) [7,8] облегчают создание платформо-зависимой модели для наиболее популярных технологических платформ.
Метамоделирование и стандарт MOF
Ранее отмечалось, что структурная часть спецификации UML используется как метамодель для пользовательской части. Теперь рассмотрим подробнее понятие метамодели и связанный с этим стандарт MOF (Meta Object Facility) [18,19]. Этот стандарт относится к семейству стандартов UML и тесно связан с остальными стандартами. Он также находится в процессе развития, текущая версия стандарта MOF 2.0 принята в октябре 2004 года.
В принятой в семействе стандартов UML объектной модели у каждого объекта имеется определённый тип. Подобно типам данных, типы объектов (называемые классами) группируют множества объектов, имеющих сходные свойства. При таком подходе объект представляется в виде одного из значений соответствующего типа, то есть как экземпляр своего класса. Каждый объект, как правило, отражает некоторую сущность реального мира и существует во время работы программы, совокупность объектов определяет состояние программы в какой-либо момент времени. Совокупность классов, описание их свойств и связей между ними задаёт функциональность программы, и является моделью программы. Но каждый класс задаётся с помощью некоторого языка, и с точки зрения этого языка является базовым элементом, то есть объектом - а значит, тоже имеет тип, называемый метаклассом. Метакласс - это конструкция языка моделирования (или программирования), с помощью которой задаются классы. Совокупность метаклассов, задающих язык моделирования, назовём метамоделью. Но язык моделирования тоже задаётся с помощью некоторого формального языка, что даёт нам ещё один уровень - уровень мета-метамоделей.
Итак, множество объектов, существующих в рамках программы в некоторый момент времени, определяет состояние программы. Множество классов, описывающих эти объекты, определяет модель программы. Конструкции языка моделирования (программирования), которые используются для задания классов, представляют собой метамодель. И, наконец, описание языка, использующегося для задания языка моделирования, называется мета-метамоделыо. Подобно тому, как объект является экземпляром класса (а класс - типом объекта), модель является экземпляром некоторой метамодели. То, что является метамоделью с одной точки зрения, может быть моделью с другой. Например, при разработке инструмента моделирования пользовательские модели - это базовые сущности или объекты, а описание языка моделирования - это модель разрабатываемого инструмента.
Цепочку метауровней можно было бы продолжать до бесконечности. Однако разработчики семейства стандартов UML решили, что для всех практических целей достаточно четырёх уровней. Поэтому в стандарте MOF описана четырёхуровневая концепция метамоделирования [20]. Для краткости уровни называют МО, Ml, М2 и МЗ, где МО - уровень объектов, а МЗ - самый абстрактный уровень мета-метамоделирования. Как правило, языки более высоких метауровней имеют более простую синтаксическую структуру, содержат меньшее число языковых конструкций. По мере же спуска по иерархии языки усложняются и специализируются для решения какой-то задачи, а также увеличивается число самих языков. Тем самым, пользователю предоставляются возможности, соответствующие его потребностям, но при этом сохраняется общая форма для описания языков, имеющая достаточно простую синтаксическую структуру.
Уровень МЗ является основополагающим в иерархии стандартов UML. Назначение этого уровня — описание языка спецификации метамоделей, то есть языка для описания других языков моделирования. В стандарте MOF для этого предлагается использовать конструкции структурной части спецификации UML. С помощью структурной части UML можно описать сам язык UML, то есть уровень МЗ в семействе стандартов UML замыкается сам на себя. Тем самым, обосновывается отсутствие необходимости в более высоких уровнях метамоделирования.
Метамодель уровня М2 - это экземпляр мета-метамодели, то есть каждый элемент метамодели — экземпляр некоторого элемента мета-метамодели. Основное назначение уровня метамоделей - описание языков моделирования, специализированных для различных задач. Описание способов моделирования и диаграмм, содержащиеся в пользовательской части спецификации UML - это пример метамоделей.
Модель уровня Ml - это экземпляр некоторой метамодели уровня М2. На этом уровне находятся пользовательские модели, отображающие конкретные прикладные системы и программы. На этом уровне происходит переход от языков моделирования, разработкой которых занимаются компании-создатели сред разработки, к моделям, создаваемым программистами для разработки конкретных программных систем. Любая пользовательская модель, написанная на UML, является экземпляром одной из метамоделей семейства UML. Кроме того, модели UML могут содержать примеры и «мгновенные отображения» состояния моделируемой системы, то есть в этих моделях могут так же использоваться примеры объектов этапа выполнения.
В самом низу иерархии находится уровень МО — уровень состояния программы в процессе её выполнения. Примеры состояний, присутствующие на уровне Ml — это ограниченные варианты сущностей этапа выполнения МО. Непосредственно уровень МО почти никогда не моделируется программистом, объекты (и «модели») этого уровня создаются во время выполнения программы.
Блок и описание трансформации
Теперь, когда мы рассмотрели, как выглядит отдельное правило трансформации, следует описать, каким образом с помощью таких правил можно задавать описания трансформаций.
Трансформацию модели в разработанном языке предлагается задавать с помощью набора правил. В то время как каждое правило задаёт преобразование какого-то фрагмента или нескольких фрагментов сходной структуры, список правил может задать преобразование всех фрагментов модели, то есть трансформацию модели в целом. За счёт того, что правила могут применяться несколько раз (если в модели несколько подходящих фрагментов) или не применяться вообще (если таких фрагментов не нашлось), одно и то же описание трансформации может использоваться для разных моделей, имеющих общую метамодель.
Если вернуться от рассмотрения абстрактных моделей к моделям программных систем в рамках технологии MDA, то отдельное правило может описывать соответствие между какими-то понятиями, концепциями или сущностями программных платформ или технологий, для которых пишется трансформация. А вся трансформация — это, соответственно, набор соответствий для всей совокупности понятий и сущностей, присущих данным технологиям. Такой подход часто используется в различных рекомендациях и инструкциях по разработке программ на той или иной технологической платформе. Обычно при этом определяется некоторое понятие или характерная задача, и описывается её стандартное решение на данной платформе. В языке UML даже введено специальное понятие «профилей» (profiles), содержащих описание понятий, характерных для той или иной технологии. То есть по своей сути они близки к трансформационным правилам. Разумеется, такие инструкции предназначены для программистов и написаны на неформальном языке. Но то, что язык описания трансформаций имеет сходную структуру, позволяет относительно легко формализовать такого рода инструкции в виде правил, что позволяет затем их автоматическое применение.
Сложные описания трансформации могут состоять из сотен правил, поэтому для простоты их написания и понимания необходимо дополнительно структурировать описания трансформации. Всё множество правил трансформации предлагается разбивать на блоки, так чтобы правила в каждом блоке по возможности слабо зависели от других блоков, и каждый блок имел свою функцию в описании трансформации. Введение дополнительного уровня иерархии - блока - облегчает понимание трансформации человеком, а также позволяет комбинировать трансформации из существующих блоков. Например, можно объединить в одной трансформации блок, генерирующий новую модель по существующей, блок, преобразующий эту модель к какому-то определённому виду, и блок, проверяющий результат на соответствие каким-либо критериям, заданным в виде набора правил.
Итак, описание трансформации на предложенном языке представляет собой последовательность блоков. Каждый блок имеет уникальное (во множестве имён блоков) имя и состоит из последовательности правил трансформации. transformation_definition::= block_definition ; block_definition::=stage name {( transformation_rule ) };
Наследование реализации в CORBA-системе и необходимая для этого трансформация моделей
Прежде, чем рекомендовать язык трансформации к применению, необходимо сравнить его способность к выражению трансформаций моделей с другими языками. Мы должны быть уверены в том, что с его помощью можно выразить и выполнить любую трансформацию, которая может быть задана на другом алгоритмическом языке. Сформулируем следующее утверждение:
Если для некоторого преобразования моделей существует алгоритм, позволяющий по исходной модели получить преобразованную модель, то существует описание трансформации на предложенном языке, дающее при выполнении такой о/се результат, что и применение данного алгоритма.
В такой формулировке это утверждение не является теоремой и не может быть строго доказано, так как содержит неформализованное понятие «алгоритм». Но в программировании существует ряд работ, направленных на формализацию понятия алгоритма. В частности, мы будем использовать формализацию понятия алгоритма через концепцию машины Тьюринга [40]. То есть мы будем считать алгоритмом такую последовательность действий по преобразованию исходных данных, для которой существует машина Тьюринга, дающая эквивалентный результат. Языки, с помощью которых можно задать любой алгоритм из определённого таким образом множества, принято называть алгоритмически полными.
Концепция машины Тьюринга (и программы машины Тьюринга) часто используется для формализации понятия алгоритма, и доказана его эквивалентность другим аналогичным алгоритмическим языкам. В то же время его простая структура, малое количество понятий и высокий уровень формализации позволяет относительно легко реализовать его с помощью языка трансформации.
Определение машины Тьюринга Машиной Тьюринга Г называется тройка множеств (A,Q,P) , где A = {a0r a.i...an} -внешний алфавит машины Т; Q = ІЯ.О/ Чі-ЧтУ - алфавит внутренних состояний или внутренний алфавит машины Т; Р - программа машины Г, состоящая из множества правил. Каждое правило состоит из левой части - пары (a,q), где a belongsto Аид belongsto Q, и правой части - тройки (a ,q ,d), где а belongsto A, q belongsto Q, a d принимает одно из трёх значений R,L,S. Причём для каждой пары элементов внешнего и внутреннего алфавита (a±/qj) , 1=1... п, j=0...m существует ровно одно правило с такой левой частью.
Машинное слово - слово вида Cq±ajB, где 1=0. .п, j=0. .m, а С и В -некоторые слова в алфавите А. Для машинного слова М = Cq±ajB и машины Г обозначим через МТ слово, полученное по следующим правилам: І.при 1=0 МТ =М; 2. для 1 0 рассмотрим правило с левой частью (a qi); пусть оно имеет правую часть (a q d): - если d=Sто МТ =Cq а. В; - если d=R то МТ =Са q B в случае, если В не пусто, и МТ =Са q а.О, если В пусто; - если d=L и С не пусто (то есть С можно представить в виде С а, ), то MT =C q a а В; - если d=L и С пусто, то МТ = q аОа В.
Через МТ(1) обозначим слово, полученное из слова М за один шаг работы машины Тьюринга, то есть МТ(1)=МТГ. Через МТ(п) обозначим слово, полученное за п шагов работы машины, МТ(п) = (МТ (п-1)) . Будем говорить, что машина Г перерабатывает машинное слово М в Ml, если найдётся такое натуральное п, что МТ(п)=М1.
Слово В в алфавите А называется результатом применения машины Г к входному слову С в алфавите Д если существует натуральное п, такое что (qiC) Т (п) =В qOB , где В=В В , и ни для какого к п машинное слово (qlC) Т(к) нельзя представить в виде L qOL , где L и L - слова во входном алфавите А. Если такого п не существует, говорят, что машина Г, применённая к слову С, работает вечно.
Существует также неформальное определение машины Тьюринга как абстрактного устройства, состоящего из бесконечной ленты, в ячейках которой могут храниться символы алфавита, автомата, который может перемещаться по ячейкам ленты, считывать и записывать их значение, внутренней памяти, в которой хранится текущее состояние машины, и программы машины Тьюринга, определяющей её поведение.
Преобразование машинных слов в модели
Машина Тьюринга применяется к машинным словам, а описания трансформации -к моделям. Поэтому, нам следует определить, каким образом машинное слово может быть преобразовано в модель. При описании трансформации для задания машинных слов будем использовать метамодель, показанную на рис. 15.
