ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА

ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА

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

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

Грамматика Ван-Вайнгаардена есть шестерка G ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА = (VZ, VM, S, R, P, S), при этом

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

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

(iii) S - алфавит, именуемый алфавитом базисных либо терминальных знаков, таковой ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА что VM Ç S = Æ;

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

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

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

Пусть G = (VZ, VM, S, R, P, S) - грамматика Ван-Вайнгаардена. Тогда назовем GA = (VM, VZ, R, A) - грамматикой, ассоциированной с метапоня­тием ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА A Î VM. Грамматика GA - контекстно-свободная и порождает контек­стно-свободный язык L(GA) Í . Из схем продукций получают с помо­щью контекстно-свободного языка L(GA), A Î VM, продукции, которые по­том применимы в выводах. Чтоб из некой схемы продукции полу­чить продукцию, следует все встречающиеся метапонятия согласованно поменять словами из ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА языка L(GA). Это означает, что если некое метапо­нятие A встречается неоднократно, то все встречаемые A должны быть за­менены одним и этим же словом из L(GA).

Как ранее, будем писать для (, b1), …,(, bn) Î P также ::= b1 | … | bn и для (A, a1), …,(A, an) Î R ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА также A::= a1 | … | an.

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

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

= ® h(b) .

(Для различения метапродукций от схем продукций будем записывать продукции ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА в виде: < > ® .)

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

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

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

L(G) = S Þ* w.

При всем этом Þ* есть рефлексивное и транзитивное замыкание ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА дела Þ и именуется отношением вывода.

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

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

Подтверждение. Пусть ::= bi1 | … | , 1 £ i £ n, – продукции контек­стно-свободной грамматики G, записанные в обычной форме Бэкуса, - исходная переменная G, VZ - алфавит с ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА wi Î , 1 £ i £ n и S - тер­миналь­ный алфавит. Тогда грамматика Ван-Вайнгаардена G = (VZ, Æ, S, Æ, P, ), при этом P точно содержит продукции в нормаль­ной форме Бэкуса в G, порождает тот же самый язык. □

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

Пусть G = (VZ, VM, S, R ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА, P, S) - грамматика Ван-Вайнгаардена. Все встре­чающиеся огромные буковкы есть метапонятия в VM, все встречающиеся малень­кие буковкы и особые знаки есть синтаксические знаки в VZ либо терми­нальные знаки в S, S обозначается как . Тем должны быть только заданы огромного количества R и P. Сейчас при ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА помощи приме­ров покажем, как определенные синтаксические конструкции языков (язы­ков программирова­ния) могут быть представлены при помощи грамматики Ван-Вайнгаардена, со­ответственно как при помощи этой грамматики могут быть вычислены функ­ции. Контекстно-свободные грамматики для этого очень слабы.

Пример 2.1. Пусть L = b … b d … d ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА . Слова ai могут пони­маться как обозначения переменных в блоке объявления переменных, слова b - как разделительные знаки и d - как правые части присваиваний. Таким макаром, L содержит в точности те «куски» программки, в каких все объявленные переменные различно обозначены и в каких объявлены все переменные, встречающиеся в левой части присваивания ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА.

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

K::= aK | a, K1::= K | e, K2::= K | e,
L::= KbL | Kb, L1::= L | e, L2::= L | e.

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

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

::= b , ::= b, ::= a,

::= a,

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

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

не лежит вK2bL>::= не равно K2> не лежит в L>,

не лежит в K2b>::= не равноK2>,

не равноK1>::= e,

не равноK1K>::= e,

<применитьL1KbL2>::= d <применитьL1KbL2> | d.

Получим:

L(Gk) = i ³ 1, L(GL) = ik ³ 1, 1 £ k £ n, n ³ 1.

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

<начало> ® <проверитьa2bab> <применитьa ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА2bab> по­этому L Þ* a2bab (в GL);

<проверитьa2bab> ® не лежит вab> <проверитьab>, потому K Þ* a2, L Þ* ab (в GK, GL);

не лежит вab> ® не равноa>, потому K1Þ* a2, K2Þ* a;

не равноa> ® e, потому K1 Þ* a, K Þ* a;

<применитьa2bab> ® d <применитьa2bab ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА>, потому L1 Þ* e, K Þ* a2, L2 Þ* ab;

<применитьa2bab> ® d, потому L1 Þ* e, KÞ* a2, L2 Þ* ab.

Слово a2baba2dada2d выводится последующим образом (в G):

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

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

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

Þ* aababaad <применитьaabab> Þ aababaad d <приме­нить aabab ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА>

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

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

1. Выводу S Þ A1…An, Ai Î < > È S соответствует дерево вывода (1) на страничке 7.

2. Пусть выводу S Þ* a1Aa2, a ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА1, a2 Î (< > È S)*, A Î < > соответст­вует 1-ое дерево вывода (2) на страничке 7. Тогда вы­воду S Þ* a1Aa2 Þ a1A1 … Ana2, Ai Î < > È 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) = n, m ³ 0.

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

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

M::= M1 | e, N::= M ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА, S::= Sf (N, | e, T::=) T | e.

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

<начало>::= **,

::= , ::= ,

::= ,

::= 1, ::= e.

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

<начало> Þ ** Þ* 1*1*

Þ 1*1* Þ 1*1*

Þ 1*1* Þ 1*1* Þ* 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 Î S* и S Þ* w.

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

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

Пусть G = (Ф, S, P, S) - грамматика. Она ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА именуется контекстно-зави­симой, либо грамматикой Хомского типа 1 и тогда только тогда, когда ка­ждая продукция a ® b Î P:

(i) имеет вид a = a1Aa2, в случае b = a1ga2, A Î Ф, a1a2 Î 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) = anbncn . (Для подтверждения следует рас­смотреть сентенциальные формы aiAbici i ³ 1и выводимые из их формы.) Этот язык является ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА также контекстно-зависимым. Можно показать, что L(G) не является контекстно-свободным. □

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

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

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

1) прочитанный знак ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА стирается и на его месте записывается новый знак;

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

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

Машина Тьюринга может применяться для представления некой (в общем случае частичной) функции либо для акцептирования некого формального языка последующим образом ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА:

(i) Машина Тьюринга кончает свои вычисления с входным сло­вом w. Содержимое ленты по окончании вычисления значит то­гда значение функции от аргумента w, в случае, если представля­ется функция. Если должен акцептироваться язык, то слово w то­гда и только тогда содержится в языке, когда машина Тьюринга находится ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА по окончании вычисления в конечном состоянии.

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

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

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

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

(iii ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА) алфавит знаков ленты Г. При всем этом Г содержит знак пробела е и производится: S Í Г - {e};

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

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

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

(vi) огромное количество конечных состояний F ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА Í Q.

Вычисление на машине Тьюринга представляется через конфигурации, при этом конфигурация (либо ситуация) есть элемент из Г*QГ*. (При всем этом Q, Q Ç Г = Æ употребляется как алфавит). Конфигурация aqb интуитивно оз­начает, что машина Тьюринга находится в состоянии q, что ab есть содер­жимое ленты и ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА что головка чтения-записи читает 1-ый знак слова b.

Условимся, что конфигурация aqb значит то же самое, что и конфи­гурация enaqbem, n, m ³ 0.

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

(i) aqAb  aBpb, если d ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА(q, A) = (p, B, R),

(ii) aCqAb  apCBb, если 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), aq  aBp, если d(q, e) = (p, B, R).)

Молвят ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА также, что отношение  прямо переводит одну конфигурацию в другую. Отношение  переводит некую конфигурацию в другую.

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

Машина Тьюринга Т останавливается при вводе слова (w1, …, wn), wi ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА Î S*, 1 £ i £ n в конечной конфигурации aqb, когда

q0w1ew2e … ewn  aqb.

Пусть h: G* ® (G - {e})* - гомоморфизм, который определен через h(A) = A, A Î G - {e}, h(e) = e. Пусть T - некая машина Тьюринга и n ³ 0. n-местная частичная функция fT,n: (S*)n ® G*, которая представля ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА­ется (либо рассчитывается) машиной T, задается как:

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

fT,n(w1, …,wn) = f(w1, …,wn),

для всех (w1, …, wn) Î (S*)n.

Отчасти вычислимая по Тьюрингу функция именуется вполне вычислимой по ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА Тьюрингу, если T останавливается для всех входных слов (w1, …, wn) Î (S*)n.

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

L = w .

Формальный язык над S именуется перечислимым по Тьюрингу, если он принимается некой машиной Тьюринга. Он именуется разреши­мым по Тьюрингу, если он принимается некой ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА машиной Тьюринга, ко­торая останавливается для всех входных слов w Î S*.

Пример 2.6. Мы желаем выстроить машину Тьюринга T, которая при­нимает формальный язык anbncn :

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

Q = (q0, q1, q2, q3, q4, q5, q6, q7, qf), S = {a, b, c}, G = (a, b, c, X ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА, e}, F = {qf};

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

d(q0, a) = (q1, a, R) d(q1, a) = (q1, a, R) d(q1, b) = (q2, b, R) d(q2, b) = (q2, b, R) d(q2, c) = (q3, c, R) d(q3, c) = (q3, c, R) d(q3, e ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА) = (q4, e, L) Проверка, выполнено ли w Î a+b+c+. Если да, то T перебегает в состояние q4. В неприятном случае T останавли­вается в одном из состояний q0, q1, q2 либо q3, не акцептируя слово.
d(q4, X) = (q4, X, L) d(q4, c) = (q5, X, L) Головка передвигается влево ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА до знака c. Он заменяется на X.
d(q4, e) = (qf, e, R) При пробеге на лево в состоянии q4 на ленте находятся только знаки X. T акцептирует слово.
d(q5, c) = (q5, c, L) d(q5, X) = (q5, X, L) d(q5, b) = (q6, X, L) Головка ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА передвигается далее влево до знака b, который заменяется на X.
d(q6, b) = (q6, b, L) d(q6, X) = (q6, X, L) d(q6, a) = (q7, X, R) Головка передвигается далее до знака a, который заменяется на X.
d(q7, X) = (q7, X, R) d(q7, b) = (q ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА7, b, R) d(q7, c) = (q7, c, R) d(q7, e) = (q4, e, L) Головка ворачивается на самый последний справа знак X, и T опять попадает в состояние q4.

Если в состоянии q4 будет найден один из знаков a либо b, то T оста­навливается, не акцептируя слово ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА. Так как тогда число знаков a либо b во входном слове больше, чем число знаков c. Если в состоянии q5 либо q6 не будет найдено b либо a, то аналогично T останавливается, не акцепти­руя слово, потому что тогда число знаков c во входном слове больше, чем количество b либо a ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА.

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

q0aaabbbccc * aaabbbсссq3  aaabbbccq4c 

 aaabbbcq5cX * aaabbq5bccX  aaabq6bXccX *

* aaq6abbXccX  aaXq7bbXccX * aaXbbXccq4X 

 aaXbbXcq4cX  aaXbbXq5cXX * aaXbq5bХcXX 

 aaXq6bXXcXX * aq6aXbXXcXX  aXq7XbXXcXX *

* aXXbXXcXq4X * aXXbXXq4cXX  aXXbXq5XXXX *

* aXXq5bXXXXX  aXq6XXXXXXX * q6aXXXXXXXX 

* Xq ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА7XXXXXXXX * XXXXXXXXq4X * q4eXXXXXXXXX 

 qfXXXXXXXXX.

Акцептирование anbncn просит O(n2) шагов. □

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

T = (Q, S, Г, d, q0, F),

где Q = (q0, q1, q2, q3), S = {a}, G ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА = (a, 0, 1, e}, F = Æ;

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

d(q0, e) = (q2, 0, L) При вводе e = а0 ворачивается 0.
d(q0, a) = (q1, a, R) d(q1, a) = (q1, a, R) d(q1, 0) = (q1, 0, R) d(q1, 1) = (q1, 1, R) d(q1, e) = (q2, e, L) Головка передвигается на последний справа ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА, хороший от е знак. Если этот знак 0 либо 1, то вычисление закончено.
d(q2, a) = (q3, e, L) d(q3, a) = (q3, a, L) Если это знак а, то он замещается на е, и головка передвигается на лево до двоичного числа, стоящего перед группой знаков а.
d(q ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА3, 0) = (q1, 1, R) d(q3, 1) = (q3, 0, L) d(q3, e) = (q1, 1, R) К этому двоичному числу добавля­ется 1.

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

 q0aaaaaa * aaaaaq2a  aaaaq3a * q3eaaaaa 

 1q1aaaaa * 1aaaaq2a  1aaaq3a * q31aaaa 

 q3e0aaaa  1q10aaaa * 1q30aaa  11q1aaa *

* 1q31aa  q ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА310aa  q3e00aa  1q100aa *

* 10q30a  101q1a * 10q31  1q300 

 11q10  110q1  11q20.

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

Как модификацию двухсторонней детерминированной машины Тью­ринга ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА разглядим одностороннюю детерминированную машину Тьюринга. Она имеет ленту, которая потенциально нескончаема исключительно в одну сторону. Конец ленты маркируется неким особым эмблемой, к примеру Z0, который не должен изменяться.

Пусть Т2 двухсторонняя машина Тьюринга. Тогда односторонняя ма­шина Тьюринга Т1 моделирует двухстороннюю машину Тьюринга Т2 сле­дующим образом. Исходный участок ленты ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА машины Т1 при необходимо­сти делится на две дорожки (т. е. алфавит ленты машины Т1 содержит Г ´ Г, где Г – алфавит ленты Т2). 2-ая дорожка служит для того, чтоб представлять содержание ячеек машины Т2, которые лежат левее той ячейки, над которой находится головка чтения-записи сначала вычисле ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА­ний. В собственном огромном количестве состояний Т1 «отмечает», находится она на верх­ней либо на нижней дорожке (т. е. огромное количество состояний машины Т1 содер­жит Q ´ {вверху, внизу}, где Q – огромное количество состояний машины Т2). Если, к примеру, машина Т2, исходя из исходной конфигурации, q0a1a2a3a4a ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА5 де­лает три шага на лево, при которых поочередно записываются знаки А1, А2, А3, то достигаемая тем конфигурация qeA3A2A1a2a3a4a5 ма­шины Т2 представляется при помощи машины Т1 последующим образом:


Если машина Т2 делает передвижение на право, то и машина Т1, если она находится ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА в состоянии (q, вверху), тоже делает движение на право. Если же машина Т1, как в прошлом примере, находится в состоянии (q, понизу), то она делает движение на лево. Схожее справедливо при пе­редвижении машины Т2 на лево. Если Т1 добивается знака Z0, то она должна перейти из состояния (q ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА, понизу) в (q, вверху), либо напротив.

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

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

Предложение 2.4.Пусть L - формальный язык. Тогда ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА последующие вы­сказывания эквивалентны:

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

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

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

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

Подтверждение.Мы покажем только моделирование действий одно­сторонней ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА машины Тьюринга T = (Q, S, Г, d, q0, F) грамматикой типа 0 G = ({S, T, $} È Q È (G - S), S, P, S). При всем этом последующие продукции ле­жат в Р:

(i) S ® TZ0q0, T ® $, T ® aTa, a Î S.

Эти продукции производят вывод S Þ* w$wRZ0q0, где w ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА Î S*.

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

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

$ ® $e.

Применяя эти продукции, мы можем моделировать деяния машины Тьюринга Т: S Þ* w$ q и тогда только тогда, ко­гда q0Z0w *a1qa2.

(iii) qz ® q, zq ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА ® q, $q ® e, q Î F, z Î G.

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

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

d(q, A1, …, Ak) = (p, B1, …, Bk, S1, …, Sk),

где q, p Î Q, Ai, Bi Î G, Si Î {L, S, R}.

(Также и в ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА рассматривающихся до сего времени моделях машин Тьюринга воз­можно допустить отсутствие передвижения головки чтения-записи при прямом переходе. Тем вычислительная «сила» машины Тьюринга не увеличивается – только-только «программирование» становится удобней.)

Конфигурация k-ленточной машины Тьюринга есть элементы из (Q ´ (G*¸G*)k. При всем этом особый знак ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА ¸ обозначает положение го­ловки чтения-записи на соответственной ленте. Таким макаром, конфигу­рации имеют вид:

(q, a1¸b1, a2¸b2, …, ak¸bk).

Входное слово (w1, …, wn) представляется конфигурацией (q0, ¸w1e … ewn, ¸, …, ¸). Переход от одной конфигурации к другой осуще­ствляется детерминированным образом при ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА помощи функций перехода. Ос­тальные определения, которые относятся к машинам Тьюринга, перено­сятся аналогично.

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

Подтверждение. Пусть Т – k-ленточная машина Тьюринга. Тогда кон­фигурация машины Т может быть смоделирована обоесторонней машиной Тьюринга Т1, лента которой разбита на 2k ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА дорожек:


Дорожка «лента i» содержит содержимое i-той ленты машины Т1, до­рожка «головка i» маркирует позицию i-той дорожки, в какой находится головка чтения-записи машины Т. В состояниях машины Т1 хранится ин­формация о том, находится знак Х на дорожке «головка i» слева либо справа от ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА головки чтения-записи машины Т1. Не считая того, соответствую­щие состояния машины Т хранятся в машине Т1. Для моделирования пере­хода машины Т машина Т1 должна отыскать знак Х на дорожке «головка i» и лежащий под ним знак на дорожке «лента i» занести как информацию в состояние. После просмотра ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА всех k дорожек машина Т1 знает, как необходимо поменять k знаков и как необходимо выверить позиции знака Х. Тогда не­обходимо опять отыскать знак Х на до­рожке «головка i», лежащий под ним знак поменять согласно функции пе­рехода машины Т и двинуть по мере надобности знак Х. После того ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА как это проделано для всех дорожек, Т1 находится в конфигурации, которая представ­ляет последовательность конфигураций машины Т. Очевидно, на каждом ша­ге необходимо смотреть за тем, чтоб информация о том, находится знак Х на до­рожке «головка i» слева либо справа от головки чтения-записи машины ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА Т1, была занесена в новое состояние. □

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

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

T = (Q, S, Г, d, q0, F),

где Q = (q0, q1, q2, qf), S = {a ГРАММАТИКИ, МАШИНЫ ТЬЮРИНГА, b, c}, G = (a, b, c, e}, F = {qf}.

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


grafik-provedeniya-meropriyatij-v-ramkah-akcii-pedagogicheskij-marafon-2013-stranica-2.html
grafik-provedeniya-onlajn-konkursa-sok-stan-odnoj-komandoj.html
grafik-provedeniya-regionalnih-ekzamenov-v-4-h-7-h-8-h-klassah-obsheobrazovatelnih-uchrezhdenij-goroda-orenburga-v-2012-2013-uchebnom-godu.html