Грамматики, машины тьюринга

И ПЕРЕЧИСЛИМЫЕ ЯЗЫКИ

 

Контекстно-свободные грамматики недостаточно «сильны» в смысле порождающей способности, чтобы учесть все синтаксические правила языка программирования (так, все встречающиеся переменные должны быть объявлены) или чтобы вычислить относительно простые функции (например, { | n ³ 0}). Поэтому как обобщение контекстно-свободных грамматик введем грамматику Ван-Вайнгаардена.

Грамматика Ван - Вайнгаардена есть шестерка G = (V_Z, V_M, S, R, P, S), причем

(i) V_Z – алфавит, называемый алфавитом синтаксических знаков, кото­рый не содержит <, >;

(ii) V_M – конечное множество (которое может быть и пустым), называе­мое множеством метапонятий, где V_M Ç (V_Z È {<, >}) = Æ и V = V_M È V_Z;

(iii) S - алфавит, называемый алфавитом базовых или терминальных символов, такой что V_M Ç S = Æ;

(iv) R Ì V_M ´ V ^* - конечное множество метапродукций;

(v) P Ì < V ^*> ´ (< V ^*> È S)^* - конечное множество схем продукций;

(vi) S Î < > - стартовая переменная.

Пусть G = (V_Z, V_M, S, R, P, S) - грамматика Ван-Вайнгаардена. Тогда назовем G_A = (V_M, V_Z, R, A) - грамматикой, ассоциированной с метапоня­тием A Î V_M. Грамматика G_A - контекстно-свободная и порождает контек­стно-свободный язык L (G_A) Í . Из схем продукций получают с помо­щью контекстно-свободного языка L (G_A), A Î V_M, продукции, которые по­том применимы в выводах. Чтобы из некоторой схемы продукции полу­чить продукцию, следует все встречающиеся метапонятия согласованно заменить словами из языка L (G_A). Это значит, что если некоторое метапо­нятие A встречается многократно, то все встречаемые A должны быть за­менены одним и тем же словом из L (G_A).

Как ранее, будем писать для (<a>, b₁), …,(<a>, b _n) Î P также <a>::= b₁ | … | b _n и для (A, a₁), …,(A, a _n) Î R также A::= a₁ | … | a _n.

Гомоморфизм h: (V È S È {<, >})^* ® (V_Z È S È {<, >})^* называется до­пустимым (в отношении грамматики G) тогда и только тогда, когда h (a) = a, a Î V_Z È S È {<, >}, h (А) Î L (G_A), A Î V_M.

Множество продукций определяется следующим образом:

= {< h (a)> ® h (b) | <a>::= b Î P, aÎ V ^*, b Î (< V ^*> È S)^*,
h – допустимый гомоморфизм}.

(Для различения метапродукций от схем продукций будем записывать продукции в виде: < > ® .)

С помощью множеств продукций определяется прямое отношение вы­вода Þ_G (или просто Þ) над (< > È S)^*:

j Þ_G y Û j = g< >d, y = g d, < > ® Î , g, d Î (< > È S)^*.

С помощью L (G) снова обозначим язык, порожденный грамматикой G:

L (G) = { w Î S^* | S Þ^* w }.

При этом Þ^* есть рефлексивное и транзитивное замыкание отношения Þ и называется отношением вывода.

Формальный язык L Í S^* называется перечислимым, если существует грамматика Ван-Вайнгаардена, такая что L = L (G).

Предложение 2.1. Любой контекстно-свободный язык перечислим.

Доказательство. Пусть < w_i >::= b _{i 1} | … | , 1 £ i £ n, – продукции контек­стно-свободной грамматики G, записанные в нормальной форме Бэкуса, < w ₁> - начальная переменная G, V_Z - алфавит с w_i Î , 1 £ i £ n и S - тер­миналь­ный алфавит. Тогда грамматика Ван-Вайнгаардена G = (V_Z, Æ, S, Æ, P, < w ₁>), причем P точно содержит продукции в нормаль­ной форме Бэкуса в G, порождает тот же самый язык. □

Чтобы избежать повторов в примерах, условимся о следующем.

Пусть G = (V_Z, V_M, S, R, P, S) - грамматика Ван-Вайнгаардена. Все встре­чающиеся большие буквы есть метапонятия в V_M, все встречающиеся малень­кие буквы и специальные знаки есть синтаксические знаки в V_Z или терми­нальные символы в S, S обозначается как <начало>. Тем самым должны быть только заданы множества R и P. Теперь с помощью приме­ров покажем, как определенные синтаксические конструкции языков (язы­ков программирова­ния) могут быть представлены с помощью грамматики Ван-Вайнгаардена, со­ответственно как с помощью этой грамматики могут быть вычислены функ­ции. Контекстно-свободные грамматики для этого слишком слабы.

Пример 2.1. Пусть L = { b … b d … d | i_k ¹ i_l, i_k ³ 1 для 1 £ k, l £ n, k ¹ l, j_s Î { i_k | 1 £ k £ n }, 1 £ s £ m, m, n ³ 1}. Слова aⁱ могут пони­маться как обозначения переменных в блоке объявления переменных, слова b - как разделительные знаки и d - как правые части присваиваний. Таким образом, L содержит в точности те «куски» программы, в которых все объявленные переменные различно обозначены и в которых объявлены все переменные, встречающиеся в левой части присваивания.

Метапродукции в R заданы посредством:

K::= aK | a, K ₁::= K | e, K ₂::= K | e,
L::= KbL | Kb, L ₁::= L | e, L ₂::= L | e.

Схемы продукций в P заданы посредством:

< начало >::= < L > < проверить L > < применить L >,

< KbL >::= < K > b < L >, < Kb >::= < K > b, < aK >::= a < K >,

< a >::= a,

< проверить KbL >::= < K не лежит в L > < проверить L >,

< проверить Kb >::= e,

< K ₁ не лежит в K ₂ bL >::= < K ₁ не равно K ₂> < K ₁ не лежит в L >,

< K ₁ не лежит в K ₂ b >::= < K ₁ не равно K ₂>,

< K ₁ K не равно K ₁>::= e,

< K ₁ не равно K ₁ K >::= e,

< применить L ₁ KbL ₂>::= < K > d < применить L ₁ KbL ₂> | < K > d.

Получим:

L (G_k) = { aⁱ | i ³ 1}, L (G_L) = { b … b | i_k ³ 1, 1 £ k £ n, n ³ 1}.

Зададим некоторые продукции в :

< начало > ® < a ² bab > < проверить a ² bab > < применить a ² bab > по­этому L Þ^* a ² bab (в G_L);

< проверить a ² bab > ® < a ² не лежит в ab > < проверить ab >, поэтому K Þ^* a ², L Þ^* ab (в G_K, G_L);

< a ² не лежит в ab > ® < a ² не равно a >, поэтому K ₁Þ^* a ², K ₂Þ^* a;

< a ² не равно a > ® e, поэтому K ₁ Þ^* a, K Þ^* a;

< применить a ² bab > ® < a ²> d < применить a ² bab >, поэтому L ₁ Þ^* e, K Þ^* a ², L ₂ Þ^* ab;

< применить a ² bab > ® < a ²> d, поэтому L ₁ Þ^* e, K Þ^* a ², L ₂ Þ^* ab.

Слово a ² baba ² dada ² d выводится следующим образом (в G):

< начало > Þ < aabab > < проверить aabab > < применить aabab >

Þ^* aabab < проверить aabab > < применить aabab > aаbab < aa не лежит в ab > < проверить ab > < применить aabab >

Þ^* aabab < проверить ab > < применить aabab > Þ aabab < при­менить aabab >

Þ^* aababaad < применить aabab > Þ aababaad < a > d < приме­нить aabab >

Þ aababaadad < применить aabab > Þ^* aababaadadaad. □

Каждому выводу в грамматике Ван-Вайнгаардена G = (V_Z, V_M, S, R, P, S) можно сопоставить направленное дерево, узлы которого маркированы с помощью элементов из множества < > È S.

1. Выводу S Þ A ₁… A_n, A_i Î < > È S соответствует дерево вывода (1) на странице 7.

2. Пусть выводу S Þ^* a₁ A a₂, a₁, a₂ Î (< > È S)^*, A Î < > соответст­вует первое дерево вывода (2) на странице 7. Тогда вы­воду S Þ^* a₁ A a₂ Þ a₁ A ₁ … A_n a₂, A_i Î < > È S соответствует вто­рое дерево вывода (2) на странице 8.

Как и ранее, получают результат дерева вывода.

Пример 2.2. Выводу в примере 2.1 соответствует дерево вывода:

 

 

 

Пример 2.3. Функция Аккерманна f: ¥ ´ ¥ ® ¥ определяется следую­щим образом:

Справедливо следующее:

f (1, 1) = f (0, f (1, 0)) = f (0, f (0, 1)) = f (0, 2) = 3.

Мы хотим «вычислить» функцию Аккерманна посредством некоторой грамматики Ван-Вайнгаардена G, то есть должно выполняться:

L (G) = {1 ^m 1 ⁿ 1 ^{f ( m , n )} | n, m ³ 0}.

(Число n представляется в виде 1 ^{n .})

Метапродукции в R заданы посредством:

M::= M 1 | e, N::= M, S::= Sf (N, | e, T::=) T | e.

Схемы продукции в P заданы посредством:

< начало >::= < M >*< N >*< f (M, N)>,

< Sf (, N) T >::= < SN 1 T >, < Sf (M 1,) T >::= < Sf (M, 1) T >,

< Sf (M 1, N 1) T >::= < Sf (M, f (M 1, N)) T >,

< N 1>::= < N >1, <e>::= e.

Слово 1*1*111 выводится следующим образом:

< начало > Þ <1>*<1>*< f (1, 1)> Þ^* 1*1*< f (1, 1)>

Þ 1*1*< f (, f (1,))> Þ 1*1*< f (, f (, 1))>

Þ 1*1*< f (, 11)> Þ 1*1*<111> Þ^* 1*1*111. □

Введем теперь грамматики, которые будут рассматриваться как обоб­щение контекстно-свободных грамматик. Грамматика G задана посредст­вом G = (Ф, S, P, S), причем:

(i) Ф – алфавит, называемый алфавитом переменных (англ. nontermi­nals).

(ii) S– алфавит, называемый алфавитом терминальных символов (англ. terminals), причем Ф Ç S = Æ (пустое множество). Посредст­вом V = Ф È S обозначается совокупный алфавит.

(iii) Р – конечное множество продукций или правил замещения (англ. productions) вида a ® b, причем a Î V ⁺ и b Î V ^*. Таким образом, Р есть конечное отношение над V ^*.

(iv) S Î Ф переменная, называемая стартовой переменной (англ. start symbol).

Для отличия от остальных грамматик грамматику G называют также грамматикой Хомского типа 0.

Теперь мы хотим определить, какой формальный язык порождает грамматика. Для этого нам понадобится определение отношения вывода Þ, которое вводится через отношение ®.

Þ _G есть отношение над V ^*, определяемое следующим образом:

j Þ _G y тогда и только тогда, когда j = gad, y = gbd и a ® b Î P.

Как и раньше, говорят: j непосредственно выводит y или: y может быть непосредственно выведено из j.

Отношение Þ есть снова рефлексивная и транзитивная оболочка отно­шения Þ _G. Говорят также: j выводит y, или y может быть выведено из j. В случае, если ясно какая грамматика имеется в виду, вместо Þ _G и Þ можно также писать Þ и Þ^*.

Слово a Î V ^* называется сентенциальной формой, если S Þ^* a. Обо­значим через L (G) формальный язык, который порождается грамматикой G. L (G) есть множество слов

L (G) = { w | w Î S^* и S Þ^* w }.

Это означает то, что L (G) содержит в точности все те сентенциальные формы, которые являются словами над терминальным алфавитом.

Путем введения ограничений на разрешаемые продукции получают так называемую иерархию грамматик по Хомскому.

Пусть G = (Ф, S, P, S) - грамматика. Она называется контекстно-зави­симой, или грамматикой Хомского типа 1 тогда и только тогда, когда ка­ждая продукция a ® b Î P:

(i) имеет вид a = a₁ A a₂, в случае b = a₁ga₂, A Î Ф, a₁a₂ Î V ^*, g Î V ⁺;

(ii) имеет вид S ® e, в случае если S не встречается в правой части про­дукции.

Контекстно-свободные и регулярные грамматики, получаемые из грамматик типа 0 введением ограничений, называются в этой связи грам­матиками типа 2 и типа 3.

Грамматика G называется ограниченной тогда и только тогда, когда для каждого правила продукции a ® b Î P выполняется: |a| £ |b|, или, если S не встречается в правой части продукции, когда выполняется a = S и b = e.

Можно легко показать, что справедливо следующее предложение.

Предложение 2.2. Формальный язык может порождаться контекстно-зависимой грамматикой тогда и только тогда, когда он может порождаться ограниченной грамматикой. □

Формальный язык называется контекстно-зависимым, если найдется контекстно-зависимая грамматика, которая порождает этот язык.

Пример 2.4. Ограниченная грамматика G = ({ S, A, B }, { a, b }, P, S), где

P = {S ® abc, S ® aAbc, Ab ® bA, Ac ® Bbcc, bB ® Bb, aB ® aaA, aB ® aa}

порождает язык L (G) = { aⁿbⁿcⁿ | n ³ 1}. (Для доказательства следует рас­смотреть сентенциальные формы aⁱAbⁱcⁱ i ³ 1и выводимые из них формы.) Этот язык является также контекстно-зависимым. Можно показать, что L (G) не является контекстно-свободным. □

Справедливо следующее предложение.

Предложение 2.3. Формальный язык порождается грамматикой Ван-Вайнгаардена тогда и только тогда, когда он порождается грамматикой Хомского типа 0. □

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

1) прочитанный символ стирается и на его месте записывается новый символ;

2) головка чтения-записи перемещается на одну ячейку влево или вправо;

3) машина Тьюринга переходит в новое состояние.

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

(i) Машина Тьюринга заканчивает свои вычисления с входным сло­вом w. Содержимое ленты по окончании вычисления означает то­гда значение функции от аргумента w, в случае, если представля­ется функция. Если должен акцептироваться язык, то слово w то­гда и только тогда содержится в языке, когда машина Тьюринга находится по окончании вычисления в конечном состоянии.

(ii) Процесс вычислений на машине Тьюринга не прерывается. Тогда функция для аргумента w не определена. Соответственно, слово w не содержится в языке.

Двусторонняя детерминированная машина Тьюринга T = (Q, S, Г, d, q ₀, F) определяется через:

(i) конечное множество состояний Q;

(ii) входной алфавит S;

(iii) алфавит символов ленты Г. При этом Г содержит символ пробела е и выполняется: S Í Г - { e };

(iv) функция перехода в общем случае лишь частично определенная:

d: (Q - F) ´ Г ® Q ´ Г ´ {L, R};

(v) начальное состояние q ₀ Î Q;

(vi) множество конечных состояний F Í Q.

Вычисление на машине Тьюринга представляется через конфигурации, причем конфигурация (или ситуация) есть элемент из Г^* Q Г^*. (При этом Q, Q Ç Г = Æ используется как алфавит). Конфигурация a q b интуитивно оз­начает, что машина Тьюринга находится в состоянии q, что ab есть содер­жимое ленты и что головка чтения-записи читает первый символ слова b.

Условимся, что конфигурация a q b означает то же самое, что и конфи­гурация eⁿ a q b e^m, n, m ³ 0.

Один шаг вычислений машины Тьюринга T представляется отноше­нием  над конфигурациями. Это отношение определяется следующим об­разом через d:

(i) a qA b  a Bp b, если d(q, A) = (p, B, R),

(ii) a CqA b  a pCB b, если d(q, A) = (p, B, L),

A, B, C Î G, a, b Î G^*, q Î Q - F, p Î Q.

(На основе нашего соглашения выполняется:

q  peB, если d(q, e) = (p, B, L), a q  a Bp, если d(q, e) = (p, B, R).)

Говорят также, что отношение  прямо переводит одну конфигурацию в другую. Отношение  переводит некоторую конфигурацию в другую.

Конечная конфигурация есть конфигурация a qA b, такая, что d(q, A) не определена. (В случае, если q Î F, то a qA b автоматически конечная кон­фигурация.)

Машина Тьюринга Т останавливается при вводе слова (w ₁, …, w_n), w_i Î S^*, 1 £ i £ n в конечной конфигурации a q b, когда

q ₀ w ₁ ew ₂ e … ew_n  a q b.

Пусть h: G^* ® (G - { e })^* - гомоморфизм, который определен через h (A) = A, A Î G - { e }, h (e) = e. Пусть T - некоторая машина Тьюринга и n ³ 0. n - местная частичная функция f_T,n: (S^*) ⁿ ® G^*, которая представля­ется (или вычисляется) машиной T, задается как:

n -местная частичная функция f: (S^*) ⁿ ® G^* называется частично вы­числимой по Тьюрингу, если существует такая машина Тьюринга, что

f_T,n (w ₁, …, w_n) = f (w ₁, …, w_n),

для всех (w ₁, …, w_n) Î (S^*) ⁿ.

Частично вычислимая по Тьюрингу функция называется полностью вычислимой по Тьюрингу, если T останавливается для всех входных слов (w ₁, …, w_n) Î (S^*) ⁿ.

Формальный язык L Í S^*, принимаемый машиной Тьюринга T, опреде­ляется через:

L = { w | q ₀ w  a q b, w Î S^*, q Î F, a, b Î G^*}.

Формальный язык над S называется перечислимым по Тьюрингу, если он принимается некоторой машиной Тьюринга. Он называется разреши­мым по Тьюрингу, если он принимается некоторой машиной Тьюринга, ко­торая останавливается для всех входных слов w Î S^*.

Пример 2.6. Мы хотим построить машину Тьюринга T, которая при­нимает формальный язык { aⁿbⁿcⁿ | n ³ 1}:

T = (Q, S, Г, d, q ₀, F), где

Q = (q ₀, q ₁, q ₂, q ₃, q ₄, q ₅, q ₆, q ₇, q_f), S = { a, b, c }, G = (a, b, c, X, e }, F = { q_f };

Функция перехода d определена следующим образом:

 

d(q 0, a) = (q 1, a, R) d(q 1, a) = (q 1, a, R) d(q 1, b) = (q 2, b, R) d(q 2, b) = (q 2, b, R) d(q 2, c) = (q 3, c, R) d(q 3, c) = (q 3, c, R) d(q 3, e) = (q 4, e, L)	Проверка, выполнено ли w Î a + b + c +. Если да, то T переходит в состояние q 4. В противном случае T останавли­вается в одном из состояний q 0, q 1, q 2 или q 3, не акцептируя слово.
d(q 4, X) = (q 4, X, L) d(q 4, c) = (q 5, X, L)	Головка передвигается налево до символа c. Он заменяется на X.
d(q 4, e) = (qf, e, R)	При пробеге влево в состоянии q 4 на ленте находятся только символы X. T акцептирует слово.
d(q 5, c) = (q 5, c, L) d(q 5, X) = (q 5, X, L) d(q 5, b) = (q 6, X, L)	Головка передвигается дальше налево до символа b, который заменяется на X.
d(q 6, b) = (q 6, b, L) d(q 6, X) = (q 6, X, L) d(q 6, a) = (q 7, X, R)	Головка передвигается дальше до символа a, который заменяется на X.
d(q 7, X) = (q 7, X, R) d(q 7, b) = (q 7, b, R) d(q 7, c) = (q 7, c, R) d(q 7, e) = (q 4, e, L)	Головка возвращается на самый крайний справа символ X, и T снова попадает в состояние q 4.

 

Если в состоянии q ₄ будет найден один из символов a или b, то T оста­навливается, не акцептируя слово. Потому что тогда число символов a или b во входном слове больше, чем число символов c. Если в состоянии q ₅ или q ₆ не будет найдено b или a, то аналогично T останавливается, не акцепти­руя слово, так как тогда число символов c во входном слове больше, чем количество b или a.

Слово w = a ³ b ³ c ³ принимается следующим образом:

q ₀ aaabbbccc ^* aaabbbсссq ₃  aaabbbccq ₄ c 

 aaabbbcq ₅ cX ^* aaabbq ₅ bccX  aaabq₆bXccX ^*

^* aaq ₆ abbXccX  aaXq ₇ bbXccX ^* aaXbbXccq ₄ X 

 aaXbbXcq ₄ cX  aaXbbXq ₅ cXX ^* aaXbq ₅ bХcXX 

 aaXq ₆ bXXcXX ^* aq ₆ aXbXXcXX  aXq ₇ XbXXcXX ^*

^* aXXbXXcXq ₄ X ^* aXXbXXq ₄ cXX  aXXbXq ₅ XXXX ^*

^* aXXq ₅ bXXXXX  aXq ₆ XXXXXXX ^* q ₆ aXXXXXXXX 

^* Xq ₇ XXXXXXXX ^* XXXXXXXXq ₄ X ^* q ₄ eXXXXXXXXX 

 q_fXXXXXXXXX.

Акцептирование aⁿbⁿcⁿ требует O (n ²) шагов. □

Пример 2.7. Построим теперь машину Тьюринга, которая при вводе aⁿ, n ³ 0 вычисляет двоичное представление числа n как слово над {0, 1}:

T = (Q, S, Г, d, q ₀, F),

где Q = (q ₀, q ₁, q ₂, q ₃), S = { a }, G = (a, 0, 1, e }, F = Æ;

Функция перехода d определена следующим образом:

 

d(q 0, e) = (q 2, 0, L)	При вводе e = а 0 возвращается 0.
d(q 0, a) = (q 1, a, R) d(q 1, a) = (q 1, a, R) d(q 1, 0) = (q 1, 0, R) d(q 1, 1) = (q 1, 1, R) d(q 1, e) = (q 2, e, L)	Головка передвигается на крайний справа, отличный от е символ. Если этот символ 0 или 1, то вычисление закончено.
d(q 2, a) = (q 3, e, L) d(q 3, a) = (q 3, a, L)	Если это символ а, то он замещается на е, и головка передвигается влево до двоичного числа, стоящего перед группой символов а.
d(q 3, 0) = (q 1, 1, R) d(q 3, 1) = (q 3, 0, L) d(q 3, e) = (q 1, 1, R)	К этому двоичному числу добавля­ется 1.

 

Двоичное представление числа 6 вычисляется следующим образом:

 q ₀ aaaaaa ^* aaaaaq ₂ a  aaaaq ₃ a ^* q ₃ eaaaaa 

 1 q ₁ aaaaa ^* 1 aaaaq₂a  1 aaaq ₃ a ^* q ₃1 aaaa 

 q ₃ e 0 aaaa  1 q ₁0 aaaa ^* 1 q ₃0 aaa  11 q ₁ aaa ^*

^* 1 q ₃1 aa  q ₃10 aa  q ₃ e 00 aa  1 q ₁00 aa ^*

^* 10 q ₃0 a  101 q ₁ a ^* 10 q ₃1  1 q ₃00 

 11 q ₁0  110 q ₁  11 q ₂0.

Вычисление двоичного представления числа n требует O(n ²) шагов. Существует «более сложная» машина Тьюринга, которая вычисляет дво­ичное представление за O(n log n) шагов. □

Как модификацию двусторонней детерминированной машины Тью­ринга рассмотрим одностороннюю детерминированную машину Тьюринга. Она имеет ленту, которая потенциально бесконечна только в одну сторону. Конец ленты маркируется некоторым специальным символом, например Z₀, который не должен меняться.

Пусть Т ₂ двусторонняя машина Тьюринга. Тогда односторонняя ма­шина Тьюринга Т ₁ моделирует двустороннюю машину Тьюринга Т ₂ сле­дующим образом. Начальный участок ленты машины Т ₁ при необходимо­сти разделяется на две дорожки (т. е. алфавит ленты машины Т ₁ содержит Г ´ Г, где Г – алфавит ленты Т ₂). Вторая дорожка служит для того, чтобы представлять содержание ячеек машины Т ₂, которые лежат левее той ячейки, над которой находится головка чтения-записи в начале вычисле­ний. В своем множестве состояний Т ₁ «отмечает», находится она на верх­ней или на нижней дорожке (т. е. множество состояний машины Т ₁ содер­жит Q ´ {вверху, внизу}, где Q – множество состояний машины Т ₂). Если, например, машина Т ₂, исходя из начальной конфигурации, q ₀ a ₁ a ₂ a ₃ a ₄ a ₅ де­лает три шага влево, при которых последовательно записываются символы А ₁, А ₂, А ₃, то достигаемая тем самым конфигурация qeA ₃ A ₂ A ₁ a ₂ a ₃ a ₄ a ₅ ма­шины Т ₂ представляется с помощью машины Т ₁ следующим образом:

 

 

Если машина Т ₂ выполняет передвижение вправо, то и машина Т ₁, если она находится в состоянии (q, вверху), тоже выполняет движение вправо. Если же машина Т ₁, как в предыдущем примере, находится в состоянии (q, внизу), то она выполняет движение влево. Подобное справедливо при пе­редвижении машины Т ₂ влево. Если Т ₁ достигает символа Z ₀, то она должна перейти из состояния (q, внизу) в (q, вверху), или наоборот.

В конце вычислений, если должна представляться функция, все сим­волы должны быть сдвинуты на верхнюю дорожку и пары заменяются на А.

В следующем предложении мы сформулируем, что языки, принимае­мые машинами Тьюринга, есть в точности перечислимые языки.

Предложение 2.4. Пусть L - формальный язык. Тогда следующие вы­сказывания эквивалентны:

(i) Существует грамматика Ван-Вайнгаардена, которая порождает L.

(ii) Существует грамматика Хомского типа 0, которая порождает L.

(iii) Существует двусторонняя детерминированная машина Тью­ринга, которая принимает L.

(iv) Существует односторонняя детерминированная машина Тью­ринга, которая принимает L.

Доказательство. Мы покажем только моделирование действий одно­сторонней машины Тьюринга T = (Q, S, Г, d, q ₀, F) грамматикой типа 0 G = ({ S, T, $} È Q È (G - S), S, P, S). При этом следующие продукции ле­жат в Р:

(i) S ® TZ ₀ q ₀, T ® $, T ® aTa, a Î S.

Эти продукции осуществляют вывод S Þ^* w $ w ^R Z ₀ q ₀, где w Î S^*.

(ii) aq ® pb для d(q, a) = (p, b, R),

aqc ® bcp для d(q, a) = (p, b, L),

$ ® $ e.

Применяя эти продукции, мы можем моделировать действия машины Тьюринга Т: S Þ^* w $ q тогда и только тогда, ко­гда q ₀ Z ₀ w ^*a₁ q a₂.

(iii) qz ® q, zq ® q, $ q ® e, q Î F, z Î G.

Если Т достигает конечной конфигурации a₁ q a₂, q Î F, то с по­мощью продукций (i), (ii) возможен вывод: S Þ^* w $ q . С по­мощью продукций (iii) возможен следующий вывод: w $ q Þ^* w. □

Рассмотрим другую модификацию машины Тьюринга – многоленточ­ную машину. Детерминированная k-ленточная машина Тьюринга имеет k лент, потенциально бесконечных в обе стороны. Над каждой лентой нахо­дится головка чтения-записи. Функция перехода d имеет в качестве аргу­ментов соответствующее состояние и символы, читаемые на каждой из лент. Ее значения задают новое состояние, новые символы, которые запи­сываются на месте старых, и независимые друг от друга перемещения го­ловок чтения-записи, которые на каждом шаге передвигаются влево (L), вправо (R) или не передвигаются (S):

d(q, A ₁, …, A_k) = (p, B ₁, …, B_k, S ₁, …, S_k),

где q, p Î Q, A_i, B_i Î G, S_i Î {L, S, R}.

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

Конфигурация k -ленточной машины Тьюринга есть элементы из (Q ´ (G^*¸G^*) ^k. При этом специальный символ ¸ обозначает положение го­ловки чтения-записи на соответствующей ленте. Таким образом, конфигу­рации имеют вид:

(q, a₁¸b₁, a₂¸b₂, …, a _k ¸b _k).

Входное слово (w ₁, …, w_n) представляется конфигурацией (q ₀, ¸ w ₁ e … ew_n, ¸, …, ¸). Переход от одной конфигурации к другой осуще­ствляется детерминированным образом с помощью функций перехода. Ос­тальные определения, которые относятся к машинам Тьюринга, перено­сятся аналогично.

Предложение 2.5. k -ленточная машина Тьюринга (k ³ 1) может быть смоделирована двухсторонней машиной Тьюринга.

Доказательство. Пусть Т – k -ленточная машина Тьюринга. Тогда кон­фигурация машины Т может быть смоделирована двухсторонней машиной Тьюринга Т ₁, лента которой разделена на 2 k дорожек:

 

Дорожка «лента i » содержит содержимое i -той ленты машины Т ₁, до­рожка «головка i » маркирует позицию i -той дорожки, в которой находится головка чтения-записи машины Т. В состояниях машины Т ₁ хранится ин­формация о том, находится символ Х на дорожке «головка i » слева или справа от головки чтения-записи машины Т ₁. Кроме того, соответствую­щие состояния машины Т хранятся в машине Т ₁. Для моделирования пере­хода машины Т машина Т ₁ должна найти символ Х на дорожке «головка i » и лежащий под ним символ на дорожке «лента i » занести как информацию в состояние. После просмотра всех k дорожек машина Т ₁ знает, как нужно изменить k символов и как нужно выверить позиции символа Х. Тогда не­обходимо снова найти символ Х на до­рожке «головка i », лежащий под ним символ заменить согласно функции пе­рехода машины Т и сдвинуть при необходимости символ Х. После того как это проделано для всех дорожек, Т ₁ находится в конфигурации, которая представ­ляет последовательность конфигураций машины Т. Разумеется, на каждом ша­ге нужно следить за тем, чтобы информация о том, находится символ Х на до­рожке «головка i » слева или справа от головки чтения-записи машины Т ₁, была занесена в новое состояние. □

Преимущество многоленточных машин Тьюринга состоит в том, что они в общем случае быстрее, чем одноленточные.

Пример 2.8. Мы хотим построить двухленточную машину Тьюринга, которая принимает формальный язык { aⁿbⁿcⁿ | n ³ 1}:

T = (Q, S, Г, d, q ₀, F),

где Q = (q ₀, q ₁, q ₂, q_f), S = { a, b, c }, G = (a, b, c, e }, F = { q_f }.

Функция перехода d определена следующим образом:

 

d(q 0, a, e) = (q 0, a, a, R, R)

Ведущая а -группа входного слова ко­пируется на вто Поделиться: Поиск по сайту ©2015-2025 poisk-ru.ru Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование. Дата создания страницы: 2018-01-08 Нарушение авторских прав и Нарушение персональных данных

 Поиск по сайту: Читайте также: Деталирование сборочного чертежа Когда производственнику особенно важно наличие гибких производственных мощностей? Собственные движения и пространственные скорости звезд Тема 11. Банковские риски и способы их оценки Опросник «Активность повседневной жизни» Интересно: Глава 3.Что такое успех? Роль химии в жизни человека Краткий словарь жестового языка Медицинские крылатые латинские выражения Обратная связь