2. Методика выполнения

Используя материал из раздела 1, по описанию абстрактного автомата, заданному преподавателем разработать программу моделирования результирующего автомата.

1. Разработать алгоритм моделирования результирующего автомата.

2. Разработать структуру данных

3. Составить программу функционирования результирующего автомата

4. Исследовать поведение результирующего автомата на построенной модели

3. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ

Согласно методике, изложенной в разделе 2, и краткой теории из раздела 1, по описанию абстрактного автомата, заданному преподавателем разработать программу моделирования результирующего автомата при соединениях исходных автоматов с обратной связью. Исследовать поведение автомата на построенной модели. Результаты исследований оформить в виде отчета.

4. КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие объекты и функции используются для описания закона функционирования абстрактных автоматов?

2. Какие правила необходимо соблюдать при моделировании абстрактных автоматов?

3. Какое различие между абстрактными автоматами Мили и Мура?

Лабораторная работа № 6

Исследование машины Тьюринга.

Цель лабораторной работы: Получение навыков исследования машины Тьюринга.

1. Краткая теория

Машина Тьюринга является расширением модели конечного

автомата, расширением, включающим потенциально бесконечную

память с возможностью перехода (движения) от обозреваемой в

данный момент ячейки к ее левому или правому соседу.

Формально машина Тьюринга может быть описана следующим

образом. Пусть заданы: конечное множество состояний – Q, в которых может находиться

машина Тьюринга; конечное множество символов ленты – Г; функция δ (функция

переходов или программа), которая задается отображением пары из

декартова произведения Q x Г (машина находится в состоянии qi и

обозревает символ gi) в тройку декартова произведения Q х Г х {L,R}

(машина переходит в состояние qi, заменяет символ gi на символ gj и

передвигается влево или вправо на один символ ленты) –

Q x Г-->Q х Г х {L,R} один символ из Г-->е (пустой); подмножество

Σ є Г - -> определяется как подмножество входных символов ленты,

причем е є (Г - Σ); одно из состояний – q0 є Q является начальным состоянием машины.

Решаемая проблема задается путем записи конечного количества

символов из множества Σ є Г – Si є Σ на ленту: eS1S2S3S4... ... ... Sne

после чего машина переводится в начальное состояние и головка

устанавливается у самого левого непустого символа (q0,­w) –,

после чего в соответствии с указанной функцией переходов

(qi,Si) - ->(qj,Sk, L или R) машина начинает заменять обозреваемые

символы, передвигать головку вправо или влево и переходить в

другие состояния, предписанные функций переходов. Остановка

машины происходит в том случае, если для пары (qi,Si) функция

перехода не определена.

2. Методика выполнения

Используя материал из раздела 1, по описанию алгоритма выполнения некоторой операции, заданному преподавателем разработать программу моделирования машины Тьюринга.

1. Разработать алгоритм моделирования машины Тьюринга.

2. Разработать структуру данных

3. Составить программу функционирования машины Тьюринга

4. Исследовать поведение машины Тьюринга на построенной модели

3. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ РАБОТЫ

Согласно методике, изложенной в разделе 2, и краткой теории из раздела 1, по описанию алгоритма выполнения некоторой операции, заданному преподавателем разработать программу моделирования машины Тьюринга, реализующей заданную операцию. Исследовать поведение машины Тьюринга на построенной модели. Результаты исследований оформить в виде отчета.