Сучкова Л.И. Абстрактный и структурный синтез автоматов

Подождите немного. Документ загружается.

располагаться символы магазинного алфавита. Начало вспо-

могательной ленты называется дном магазина. Связь устрой-

ства управления с лентами осуществляется двумя головками,

которые могут перемещаться вдоль лент. Головка входной

ленты может перемещаться только в одну сторону - вправо

или оставаться на месте. Она может выполнять только чте-

ние. Головка вспомогательной ленты способна выполнять

как

чтение, так и запись, но эти операции связаны с переме-

щением головки определенным образом: при записи головка

предварительно сдвигается на одну позицию вверх, а затем

символ заносится на ленту, при чтении символ, находящийся

под головкой считывается с ленты, а затем головка сдвигает-

ся на одну позицию вниз, т.о. головка

всегда установлена

против последнего записанного символа. Позицию, находя-

щуюся в рассматриваемый момент времени под головкой,

называют вершиной магазина.

Определение. МП-автоматом называется кортеж

вида(A,Z,M,δ,a

,F,B), где A – конечное множество состояний

автомата, Z – алфавит, M – алфавит магазина, δ- функция пе-

реходов AxZxM→AxM, a

– начальное состояние, F – множе-

ство заключительных состояний, B – символ для обозначения

дна магазина.

МП-автомат помимо входной цепочки символов работа-

ет со вспомогательным магазином, используемым как вре-

менное хранилище данных.

Рассмотрим, каким образом МП-автоматы используются

для распознавания языков, порождаемых КС-грамматиками.

Известно, что существуют нисходящая и восходящая страте-

гии разбора. Рассмотрим

построение МП-автомата, рабо-

тающего по нисходящей стратегии, когда построение дерева

грамматического разбора начинается от аксиомы, и на каж-

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

Правила МП-автомата имеют вид:

1) занесение аксиомы в магазин в начале разбора

е е →a

2) для правила А→ t нетерминал A в магазине заменяет-

ся на зеркальное отображение правой части правила t~

е А →а

3) при нахождении в верхушке магазина терминала он

сравнивается с символом во входной цепочке, при их совпа-

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

z z →а

4) завершение разбора происходит, когда магазин пуст и

цепочка прочитана

е В →f B

Рассмотрим пример. Пусть имеется КС-грамматика, по-

рождающая формальный язык a

. Грамматика, порож-

дающая язык, имеет вид:

S → a S b | A

A → c T

T → d T | d

Построим правила МП-автомата, распознающего цепоч-

ки языка:

е е →a

e S → a

bSa

e S → a

e A → a

e T → a

a a → a

b b → a

c c → a

d d → a

e B → f B

Пусть на вход автомата подается цепочка acddb.

В начальный момент времени в магазине находится

только символ дна, затем в магазин записывается аксиома S,

заменяемая на зеркальное отображение правила aSb (рисунок

2.2).

Рисунок 2.2

После того как символ ‘a’ на входной ленте совпал с

символом в верхушке магазина, из верхушки символ выбра-

сывается и читается следующий символ с входной ленты.

Затем S заменяется на А, и А заменяется на Тс (рисунок 2.3).

Рисунок 2.3

Далее символ ‘c’в верхушке магазина совпал с символом

на ленте, он

выбрасывается из магазина и читается с ленты

символ ‘d’ (рисунок 2.4). В магазине нетерминал T заменяет-

ся на Td.

Рисунок 2.4

После выброса ‘d’ из магазина читаем следующий ‘d’ на

ленте и заменяем T в магазине на d (рисунок 2.5).

Рисунок 2.5

Далее выбрасываем d из магазина и читаем с ленты ‘b’,

который совпадает с верхушкой магазина, а значит, удаляет-

ся из верхушки, и с ленты читается пустая цепочка, а в мага-

зине остается символ дна магазина

, что служит признаком

завершения распознавания входной цепочки (рисунок 2.6).

Рисунок 2.6

Разбор по нисходящей стратегии с помощью МП-

автомата предусматривает отсутствие в грамматике леворе-

курсивных правил. Но даже при этом условии для выполне-

ния разбора необходимо предусмотреть перебор всех воз-

можных правил для нетерминала на определенном этапе раз-

бора при захождении разбора в тупик. Такой метод называет-

ся разбор с возвратом.

3 АВТОМАТЫ-ПРЕОБРАЗОВАТЕЛИ

3.1 Машина Тьюринга как универсальный тип абст-

рактного автомата-преобразователя

Универсальным способом задания преобразования це-

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

алгоритма.

Определение. Под алгоритмом неформально обычно

понимается последовательность инструкций, предназначен-

ная для некоторого устройства и определяющая процесс пе-

реработки исходных данных в требуемый результат.

При

этом требуется:

1) чтобы исходные данные были заданы во входном ал-

фавите и могли принимать значения из выходного алфавита;

2) чтобы процесс переработки данных состоял из от-

дельных дискретных шагов и был детерминированным;

3) чтобы последовательность инструкций была конеч-

ной. Необязательным свойством алгоритма является его ре-

зультативность.

Для решения любой задачи требуется

построить соот-

ветствующий алгоритм, поэтому важным является математи-

ческое доказательство факта существования алгоритма ре-

шения поставленной задачи. Однако для этого необходимо

дать точное определение алгоритма.

Было предложено несколько точных математических

моделей, уточняющих понятие алгоритма - система рекур-

сивных функций Клини, машина Тьюринга, нормальный ал-

горитм Маркова, схема Колмогорова-Успенского, лямбда -

конверсии

Черча, финитные комбинаторные процессы Поста.

Модель алгоритма, называемая машиной Тьюринга, со-

стоит из бесконечной ленты Л, разделенной на ячейки, чи-

тающей – пишущей головки Г, которая перемещается по лен-

те, и управляющего устройства. В каждой ячейке может быть

записан один символ из алфавита Z. Головка может нахо-

диться в одном из внутренних состояний

, принадлежащих

конечному множеству Q и в каждый момент времени видит

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

ном времени, по тактам. В зависимости от состояния головки

и символа, против которого она стоит, головка записывает на

ленте новый символ (или оставляет старый), переходит в но-

вое состояние (или остается в старом) и

передвигается: впра-

во (R), влево (L) или остается в прежнем положении (E).

Дадим формальное определение машины Тьюринга.

Определение. Машиной Тьюринга называется кортеж

вида (А, Z, δ, а

, f, e, z

), где А – конечное множество состоя-

ний, Z – алфавит ленты, а

– начальное состояние, f – заклю-

чительное состояние, е – символ для обозначения пустой

ячейки, z

– символ-разделитель цепочек на ленте, δ- функ-

ция переходов:

А х Z →А x Z x S.

Определение. Один элемент функции переходов называ-

ется командой машины Тьюринга:

→a

Определение. Конфигурацией машины Тьюринга называется

кортеж вида k=<αаzβ>,

где αи β- цепочки слева и справа от

головки, α,β∈Z

, а – текущее состояние машины, z – символ

под головкой.

Определение. Конфигурация k

непосредственно пере-

ходит в конфигурацию k

, если k

получена из k

с приме-

нением одной команды: k

⇒k

Определение. Конфигурация k переходит в конфигура-

цию m, если существуют промежуточные конфигурации k

…, k

, такие, что:

k⇒k

⇒k

…⇒k

⇒m.

Определение. Конфигурация, содержащая начальное со-

стояние, называется начальной, а заключительное состояние

– заключительной.

Определение. Если в начальной или заключительной

конфигурации цепочка слева от головки пуста, то такие кон-

фигурации называются стандартными.

Определение. МТ перерабатывает цепочку ϕ в цепочку

ω, если, имея на ленте цепочку ϕ и работая из начальной

конфигурации, получает на ленте цепочку ω, перейдя в за-

ключительную конфигурацию. Если начальная и заключи

тельная конфигурации стандартные, то переработка называ-

ется правильной.

Способы задания машины Тьюринга – последовательно-

стью команд, графом, таблицей.

Рассмотрим простейшую машину Тьюринга, которая,

имея на ленте последовательность символов из 0 и 1, заменя-

ет все нули на 2. Зададим машину графом, дуги которого со-

единяют состояния машины Тьюринга, на каждой дуге пи-

шется читаемый

символ в ячейке, затем заменяемый символ

и направление перемещения головки, например, “0 → 2 R”

(рисунок 3.1). Алгоритм работы машины следующий. В на-

чальном состоянии на ленте записана цепочка из 0 и 1, ма-

шина в стандартной начальной конфигурации, головка нахо-

дится над первым символом цепочки. Будем перемещать го-

ловку вправо, если на ленте прочитаем цифру 1,

оставим ее

без изменения, если прочитаем цифру 0, заменим ее на 2. Эти

действия будем повторять до тех пор, пока не прочитаем в

ячейке пустую цепочку, что означает конец нашей перераба-

тываемой цепочки. В этом случае необходимо перемещать

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

цепочку слева от результата

преобразования. Сдвинем голов-

ку на первый символ цепочки, чтобы машина завершила ра-

боту в стандартной заключительной конфигурации.

Рисунок 3.1

При задании машины Тьюринга таблицей в строках ука-

зываются состояния, в столбцах – читаемые символы. В

клетках таблицы записывается правая часть команды маши-

ны, включающая новое состояние, записываемый символ и

направление перемещения головки. Таблица переходов рас-

смотренной выше машины Тьюринга приведена на рисунке

3.2.

0 1 2

2 R a

1 R

1 L a

2 L

Рисунок 3.2

Задание машины Тьюринга последовательностью ко-

манд удобно для интерпретации команд с помощью специ-

ального программного обеспечения, позволяющего прове-

рять правильность обработки цепочек из символов входного

алфавита (см. раздел 9 настоящего учебного пособия). Ко-

манды рассмотренной машины Тьюринга:

0 → a

2 R

1 → a

1 R

ε → a

ε L

1 → a

1 L

2 → a

2 L

ε → f ε R

Так как машина Тьюринга, согласно тезису Тьюринга,

является средством реализации любого алгоритма, а алго-

ритм преобразует исходные данные в результат, то можно

считать, что машина выполняет вычисление значений функ-

ций при условии, что на ленте записаны исходные данные.

Исходные данные и результаты для функций будем хранить

на ленте в унарном коде

, то есть числу 0 соответствует пус-

тая цепочка, числу N – N единиц на ленте.

Определение. Машина Тьюринга вычисляет функцию

f(x

,…,x

), если:

1. При принадлежности аргументов области определе-

ния функции, машина, имея на ленте аргументы, разделен-

ные символом-разделителем, и начиная работу из начальной

конфигурации, переходит в заключительную конфигурацию,

оставляя на ленте результат вычислений.

2. При выборе аргументов вне области определения

функции машина Тьюринга работает бесконечно.

Рассмотрим пример вычисления функции f(x)=x/2. Оче-

видно,

что если х является нечетным, то машина Тьюринга

должна зациклиться. Возможно построить несколько машин

Тьюринга, вычисляющую данную функцию с применением

различных алгоритмов обработки исходной цепочки. Рас-

смотрим, например, такой алгоритм. Будем стирать в начале

цепочки унарного кода по 2 единицы, затем перемещать го-

ловку в конец цепочки до пустой ячейки и записывать

в нее

звездочку, а затем снова возвращаться на начало цепочки.

Если исходная цепочка содержит четное количество единиц,

то наступит момент в состоянии а

, когда в начале цепочки

единиц не будет, а на ленте останутся только звездочки, ко-

личество которых в два раза меньше, чем единиц в исходной

цепочке (рисунок 3.3).