Тема 4.4. Машина Тьюринга как автомат, реализующий

любые алгоритмы обработки информации

Машина Тьюринга является расширением модели конечного автомата, расширением, включающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу.

Формально машина Тьюринга может быть описана следующим образом. Пусть заданы: конечное множество состояний – 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) функция перехода не определена.

Примеры.

Тема 4.5. Автоматы с магазинной памятью (мп-автоматы)..

Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекст­ных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматри­вать как бесконтекстные.В отличие от конечных автоматов и преобразователей, автоматы с магазинной памятью снабжены дополнительной магазинной памятью.

Конечное  управляющее устройство снабжается дополнительной управляющей головкой, всегда указывающей на верхнюю ячейку магазинной памяти; за один такт работы автомата  (преобразователя)   управляющая головка может произвести следующие движения:           

1) стереть символ из верхней ячейки (при этом все символы, находящиеся на рабочей ленте, перемещаются на  одну  ячейку вверх);                                                       

2) стереть   символ  из  верхней ячейки  и записать  на рабочую ленту  непустую цепочку символов (при этом содержимое

рабочей  ленты сдвигается вниз ровно настолько,  какова длина

с   записываемой цепочки).

Формально детерминированный магазинный автомат определя­ется как следующая совокупность объектов:

M = (V, Q, VM, δ, q0, z0, F),

где V, Q, q0 Є Q, F определяются так же, как и для конечного автомата;

VM = {z0, z1,…,zp-1} — алфавит магазинных символов авто­мата;

δ — функция, отображающая множество Q X (V U { ε }) X VMв множество Q X VM, где е — пустая цепочка;  z0 Є VM — так называемый граничный маркер,  т. е.  символ,первым появляющийся в магазинной памяти.

Недетерминированный магазинный автомат отличается от де­терминированного только тем, что функция δ отображает множество Q X (V U { ε }) X VM. в множество конечных подмножеств Q x VM

Как и в случае конечных автоматов, преобразователи с магазинной памятью отличаются от автоматов с магазинной памятью нали­чием выходной ленты.

Далее будем рассматривать только недетерминированные магазин­ные автоматы.

Рассмотрим  интерпретацию функции δ для  такого  автомата. Эту функцию можно представить совокупностью команд вида

(q, a, z)→(q1, γ1),…,(qm, γm),

где q, q1,…qm Є Q, a Є V, z Є VM, γ1,…,γm Є V*m

При этом считается, что если на входе читающей головки авто­мата находится символ а, автомат находится в состоянии q, а верхний символ рабочей ленты z, то автомат может перейти к состоянию qi, записав при этом на рабочую ленту цепочку  γi(1 ≤ i ≤ m)вместо символа z, передвинуть входную головку на один символвправо так, как это показано на рис. 1, и перейти в состояние qi. Крайний левый символ γi должен при этом оказаться в верхней ячейке магазина. Команда (q, e, z)→(q1, γ1),…, (qm, γm) означает,что независимо от входного символа и, не передвигая входной го- +ловки, автомат перейдет в состояние qi, заменив символ z магазина на цепочку γi(1 ≤ i ≤ m).        •

Ситуацией магазинного автомата называется пара (q, γ), где

q Є Q, γ Є V*m. Между ситуациями магазинного автомата (q, γ) и

(q’, γ’),  устанавливается отношение, обозначаемое символом ├, если среди команд найдется такая, что

(q, a, z)→(q1, γ1),…,(qm, γm),

причем γ = zβ, γ’ = γiβ q' = qi для некоторого 1 ≤ i ≤ m (z Є Vm,

β Є V*m  ).

Говорят, что магазинный автомат переходит из состояния (q, γ) в состояние (q’, γ’) и обозначают это следующим образом:

a: (q, γ)├ (q’, γ’).

Вводится и такое обозначение:

a1...an: (q, γ)├ * (q’, γ’),

если справедливо, что

ai: (qi, γi)├ (qi+1, γi+1), 1 ≤ i ≤ m

где

ai Є V, γ1 = γ, γ2,…, γn+1 = γ’ Є V*m 

q1 = q, q2,…, qn+1 = q’ Є Q 

Существует два способа определения языка, допускаемого ма­газинным  автоматом.   Согласно   первому  способу  считается,   что входная цепочка α Є V* принадлежит языку L1 (M) тогда, когда после просмотра последнего символа,  входящего в эту цепочку,

в магазине автомата М будет находиться пустая цепочка ε. Другими словами,

L1 (M) = { α | α: (q0, z0) ├ * (q, ε)}

где q Є Q.

Согласно второму способу считается, что входная цепочка при­надлежит языку L2 (M) тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М окажется в одном из своих заключительных состояний qf Є F. Другими словами,

L2 (M) = { α | α: (q0, z0) ├ * (qf, γ)}

где γ Є V*m, qf Є F 

Доказано, что множество языков, допускаемых произвольными магазинными автоматами согласно первому способу, совпадает с множеством языков, допускаемых согласно второму способу.

Доказано также, что если L (G2) — бесконтекстный язык, по­рождаемый Грамматикой G2 = (Vx, VT, Р, S), являющейся нормаль­ной формой Грейбах, произвольной бесконтекстной грамматики G, то существует недетерминированный магазинный автомат М такой, что L1 (M) = L (G2). При этом

M = (V, Q, Vm , δ, q0, z0, 0),

Где V=VT; Q={q0}; VM=VN; z0=S

а для каждого правила G2 вида

A→aα, a Є VT, a Є V*n

строится команда отображения δ:

(q0, a, A)→(q0, a)

Apia логично для любого недетерминированного магазинного автомата М, допускающего язык L1 (M), можно построить бескон­текстную грамматику G такую, что L (G) = L1 (M).

Если для конечных автоматов детерминированные и недетерми­нированные модели эквивалентны по отношению к классу допускае­мых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками.