5. Упражнения

1. Постройте для входного алфавита  = {0,1} конечный автомат A, кото­рый принимает язык L = || A || = {w w  {01}^*, w – двоичное пред­ставление натурального числа, делящегося на 3}. Для простоты можно положить, что  представляет 0 и что разрешены ведущие нули.

Решение. 3 состояния Q = {0,1,2} представ­ляют классы вычетов по модулю 3. Чтение цифры 0 означает умножение на 2 по мо­дулю 3, чтение цифры 1 означает умножение на 2 и сложение с 1 по модулю 3. Это приво­дит к следующему автомату:

2. (a) Постройте наименьший недетерминированный конечный автомат A с входным алфавитом  = {a,b,c}, такой, что || A || = {a,b,c}^*abc{a,b,c}^*.

Решение.

Поскольку автомат с не более чем тремя состояниями, при­нимающий слово abc, при принятии этого слова должен делать «петлю» (т.е. по край­ней мере одно состояние в по­следовательности при принятии abc будет встречаться дважды), то должно быть принято по крайней мере одно слово длины меньше 3. Отсюда следует, что указанный автомат является наименьшим из возможных.

(b) Детерминируйте этот автомат.

Решение. Рассмотрите функцию перехода   Q    P (Q) и про­должите её до функции : P (Q)   P (Q):

	a	b	c
q0 q1 q2 q3	q0q1 ø ø q3	q0 q2 ø q3	q0 ø q3 q3
q4:  q0q1 q5:  q0q2 q6:  q0q3 q7:  q0q1q3 q8:  q0q2q3	q0q1 q0q1 q0q1q3 q0q1q3 q0q1q3	q0q2 q0 q0q3 q0q2q3 q0q3	q0 q0q3 q0q3 q0q3 q0q3

Это дает автомат:

Рассматривая состояния q₆, q₇ и q₈, можно видеть, что все эти состоя­ния являются конечными и при чтении любого из символов a, b или c автомат остается в пределах этих состояний, поэтому эти три состоя­ния могут быть объединены в состояние q:

3. Постройте детерминированный конечный автомат A, который прини­мает только те слова над алфавитом  = {0,1}, которые содержат не­четное число символов 0 и заканчиваются на 11.

Решение. Недетерминированный автомат строится непосредственно:

Детерминация этого автомата путем продолжения функции перехода дает:

	0	1
q0	q1	q0
q1	q0	q1q2
q2	ø	q3
q3	ø	ø
q4:  q1q2	q0	q1q2q3
q5:  q1q2q3	q0	q1q2q3

и отсюда:

4. Укажите конечный автомат A с входным алфавитом  = {a, b}, такой, что ||A|| = {w {a, b}^* w содержит подслово aa, но не содержит подслово bb}.

Решение. Следующая структура автомата

может быть просто продолжена до:

5. Докажите, что не существует конечный автомат A, такой, что ||A|| = L = {aⁱbⁱ i}. (Отсюда следует, что L не является регулярным.)

Доказательство. Предположим, что существует конечный автомат A = (Q,,,q₀,F) c n состояниями, такой, что L = ||A||. Для каждого при­нимаемого слова w_i = aⁱbⁱ рассмотрим последовательность состояний при принятии слова w_i: при этом через q_i обозначим состояние, которое будет достигнуто после обработки aⁱ. Так как A имеет только n состоя­ний, то отсюда следует, что по крайней мере два состояния из {q_i | 1  I  n} должны быть одинаковыми, например, должно выпол­няться: 0  q_k  q_l  n. Однако тогда A будет принимать слово a^lb^k c k  l, что является противоречием к тому, что L = || A ||.

6. Докажите, что не существует конечный автомат A с входным алфавитом Σ = {a}, такой, что ||A|| = L = {a^i² i}.

Доказательство. Предположим, что существует конечный автомат A = (Q,,,q₀,F) c n состояниями, такой, что L = ||A||. Для каждого при­нимаемого слова w_i = a^i² рассмотрим последовательность состояний, достигаемых при принятии слова w_i: при этом через q_i обозначим со­стояние, которое будет достигнуто после обработки aⁱ. Так как A обладает только n состояниями, отсюда следует, что по крайней мере два состояния из {q_i | 1  i  n + 1} должны быть одинаковыми, напри­мер: 1  q_k  q_l  n+1. Однако тогда будет приниматься слово w = a^{l² – (l – k)} c k < l из A. Справедливо также:

(l – 1)² = l² – (l – 1) – l  l² – (l – k) – l < l² – (l – k) < l²,

а это означает, что w не является квадратом ни одного натурального чис­ла и поэтому w не содержится в языке L. Это противоречие показывает, что L не может быть языком, принимаемым конечным автоматом A.

7. Укажите контекстно-свободную грамматику G с алфавитом терми­нальных символов Σ = {a, b}, такую, что L(G) = {aⁿb²ⁿ| n > 3}.

Решение. G = ({S, T}, {a, b}, P, S), причем продукции P заданы сле­дующим образом:

S → aaaaTbbbbbbbb,

T → aTbb,

T → ε.

8. Укажите контекстно-свободную грамматику G над Σ = {a, b, c}, кото­рая порождает язык L = {aⁱb^jc^k| k  i + j, i, j, k }.

Ответ. Из того соображения, что для каждого «впереди» читаемого символа a, соответственно b, «позади» может быть выведен символ c либо ε, получается грамматика G = ({S,T,C},{a,b,c},P, S), где продукции P заданы следующим образом:

S → aSC | T,

T → bTC | ε,

C → c | ε.

9. Укажите контекстно-свободную грамматику G над Σ = {a, b, c}, кото­рая порождает язык L = {aⁱb^jc^k| i, j, k  0, j = 2i или i > k}.

Ответ. Рассматривая случаи j = 2i для i  1, i = j = 0 и i > k раздельно, получим, например, грамматику G = ({S, S₁, S₂, S₃, T, U, B, C}, {a, b, c}, P, S), причем продукции P заданы следующим образом:

S → S1 | S2 | S3 S1 → aTbbS2 S2 → cS2 | ε S3 → aU

T → aTbb | ε U → aUC | B B → bB | ε C → c | ε

10. Укажите контекстно-свободную грамматику G над Σ = {a, b, c}, кото­рая порождает язык L = {aⁱb^jc^k| i  j или j  k}.

Ответ. Рассмотривая случаи i > j, j > i, j > k и k > j раздельно, получим, например, грамматику G = ({S,T,U,A,B,C}, {a,b,c}, P, S), причем про­дукции P заданы следующим образом:

S → aATC | TbBC | AbBU | AUcC T → aTb | ε U → bUc | ε

A → aA | ε B → bB | ε C → cC | ε

Замечание. Так как можно показать, что язык = { aⁱb^jc^k | i }={a, b,c}^*\L не является контекстно-свободным, здесь приведен пример, что допол­нение контекстно-свободного языка не обязано быть контекстно-сво­бодным.

11. Укажите линейно-контекстно-свободную грамматику G с алфавитом

Σ = {a, b}, которая порождает язык L = {a,b}^*\{v^m, v = aⁿb | n1, m2}.

(Грамматика называется линейно-контекстно-свободной в том случае, ес­ли она содержит только продукции вида A → a₁Ba₂ и А → a, где A, B  Ф и a,a₁,a₂  Σ ∪ { ε }.)

Решение. Можно заметить, что для каждого слова w  L выполняется по крайней мере одно из следующих условий:

(а) w содержит подслово baⁱba^jb где i  j;

(b) w начинается с aⁱba^jb, причем i  j;

(с) w начинается с b;

(d) w заканчивается на a;

(е) w содержит подслово bb;

(f) w содержит только одно b;

(g) w является пустым словом.

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

G = ({S,S₁,T₁,U₁,V₁,W₁,X₁,S₂,T₂,U₂,V₂,W₂,S₃,T₃,S₄,T₄,S₅,T₅,U₅,V₅,S₆,T₆,U₆},{a,b},P,S),

где продукции P заданы следующим образом:

S → S1 | S2 | S3 | S4 | S5 | S6 | ε S1 → S1a | S1b | X1 X1 → aX1 | bX1 | T1 T1 → bU1b | bW1b U1 → aU1 | aV1 V1 → aV1a | b W1 → W1a | V1a S2 → S2a | S2b | T2 T2 → U2b | W2b U2 → aU2 | aV2 V2 → aV2a | b W2 → W2a | V2a

S3 → bT3 T3 → aT3 | bT3 | ε S4 → T4a T4 → T4a | T4b | ε S5 → aS5 | bS5 | T5 T5 → T5a | T5b | U5 U5 → bV5b V5 → ε S6 → aS6 | T6 T6 → T6a | U6 U6 → b

12. Покажите: если L  ^* контекстно-свободный и a  , то и : = LL^Ra также контекстно-свободный (L^R = {w^R | w  L}, w^R – зеркальное отра­жение w).

Решение. Пусть язык L порождает контекстно-свободную грамматику G = (, , P, S). Легко видеть, что контекстно-свободная грамматика G^R: = (, , P^R, S), где продукции P заданы следующим образом:

T → ₁…_n  P, _i     и T    T → _n…₁  P^R,

порождает язык L^R. Обозначим теперь через  и  две независимых копии , таким образом, A    A    A   для всех A  . Тогда контекстно-свободная грамматика  = ({    S }, , {S → S S a  P   P }, S) порождает язык , причем продукции P и P определены следующим образом:

P есть копия P, где в продукциях из P каждая встречающаяся пере­менная A   замещается соответствующей переменной A  ;

P есть копия P^R, где в продукциях из P^R каждая встречающаяся пе­ременная A   замещается соответствующей переменной A  .

13. (a) Постройте для языка L={aⁿbⁿ│n } контекстно-свободную грамма­тику в нормальной форме Грайбах.

Решение. G = ({S, B}, {a, b}, P, S), где продукции P заданы посред­ством:

S → aSB │ε

B → b

(b) Укажите магазинный автомат P, который принимает язык L через конечное состояние и пустую магазинную ленту.

Решение. P= ({q}, {a, b}, {S, B}, δ, q, S, {q}), где функция перехода δ задана следующим образом:

δ(q, a, S) = {(q, SB)}
δ (q, ε, S) = {(q, ε)}
δ(q,b, B) = {(q, ε)}

Автомат представлен следующей схемой:

ε

(c) Укажите детерминированный магазинный автомат P’, который принимает язык L’= {aⁿbⁿ │n ≥ 1} через конечное состояние и пус­тую магазинную ленту.

Решение. Следует рассмотреть, к примеру, контекстно-свободную грамматику G’ = ({S, B}, {a, b}, P, S) с продукциями P:

S → aB

B → aBb│b

Эта грамматика порождает L’ и приводит к детерминированному магазинному автомату P’ = ({q}, {a, b}, {S, B, b}, δ, q, S, {q}), где функция перехода задана следующим образом:

δ(q, a, S) = {(q, B)}

δ(q, a, B) = {(q, Bb)}

δ(q, b, B) = {(q, ε)}

δ(q, b, b) = {(q, ε)}

Автомат представлен следующей схемой:

(d) Укажите детерминированный магазинный автомат P’’, который принимает язык L’’= L через конечное состояние.

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

(bbX, q1)

(bbbX, q1)

14. (a) Постройте для языка L = {waw^R│w{a, b}*} контекстно-свободную грамматику в нормальной форме Грайбах. (w = a₁a₂...a_n, a_i   w^R = a_na_n-1...a₁)

Решение. G = ({S, A, B}, {a, b}, P, S), где продукции P заданы сле­дующим образом:

S → a│aSA│bSB A → a

B → b

(b) Укажите магазинный автомат P, который принимает язык L через конечное состояние и пустую магазинную ленту.

Решение. P = ({q}, {a, b}, {S, A, B}, δ, q, S, {q}), где функция пере­хода δ задана следующим образом:

δ(q, a, S) = {(q, ε), (q, SA)}

δ(q, b, S) = {(q, SB)}

δ(q, a, A) = {(q, ε)}

δ(q, b, B) = {(q, ε)}

15. (a) Постройте для L = {ww’  {a, b}^*│w ≠w’^R и w = w’} контекстно-свободную грамматику в нормальной форме Грайбах.

Решение. G = ({S, T, A, B}, {a, b}, P, S), где продукции P заданы следующим образом:

S → aSA │ bSB │ aTB │ bTA

T → aTA │ bTB │ aTB │bTA│ε

A → a

B → b

(b) Укажите магазинный автомат P, который принимает язык L через конечное состояние и пустую магазинную ленту.

Решение. P=({q}, {a, b}, {S, T, A, B}, δ, q, S, {q}), где функция пере­хода δ задана следующим образом:

δ(q, a, S) = {(q, SA), (q, TB)}	δ(q, a, A) = {(q, ε)}
δ(q, b, S) = {(q, SB), (q, TA)}	δ(q, a, B) = {(q, ε)}
δ(q, a, T) = {(q, TA), (q, TB)}	δ(q, ε, T) = {(q, ε)}
δ(q, b, T) = {(q, TA), (q, TB)}

15. Постройте для языка L = {aⁱb^ja^k│i, j, k  0, i + k = j} магазинный авто­мат, такой, что P = L.

Решение. Следует рассмотреть контекстно-свободную грамматику G = = ({S,T, A, B}, {a, b}, P, S), где продукции P заданы следующим об­разом:

S → aBT

B → aBb │b

T → bA

A → bAa │ a

Исходя из этого строят магазинный автомат P = ({q}, {a, b}, {S, T, A, B, a, b}, δ, q, S, {q}), где функция перехода δ задана следующим образом:

δ(q, a, S) = {(q, BT)}	δ(q, b, A) = {(q, Aa)}
δ(q, a, B) = {(q, Bb)}	δ(q, a, A) = {(q, ε)}
δ(q, b, B) = {(q, ε)}	δ(q, a, a) = {(q, ε)}
δ(q, b, T) = {(q, A)}	δ(q, b, b) = {(q, ε)}

Автомат представлен следующей схемой:

17. Постройте для входного алфавита  = {a, b} магазинный автомат P, та­кой, что P = L = {w^*│w содержит одинаковое число символов a и b}.

Решение. Вариант 1. Исходя из грамматики G = ({S}, {a, b}, P, S) с продукциями P

S → aSbS │bSaS │ε

строят магазинный автомат P = ({q}, {a, b},{S, a, b}, δ, S, {q}), где функция перехода δ задана следующим образом:

δ(q, a, S) = {(q, SbS)}	δ(q, a, a) = {(q, ε)}
δ(q, b, S) = {(q, SaS)}	δ(q, b, b) = {(q, ε)}
	δ(q, ε, S) = {(q, ε)}

Вариант 2. Можно непосредственно построить магазинный автомат, если заметить, что требуется только отметить «перевес» символов a или b на магазинной ленте. Это приводит к автомату P = ({q}, {a, b}, { p_0, p_1, p₂}, δ, p₀, {q}), где:

δ(q, a, p0) = {(q, p1p0)}	δ(q, b, p0) = {(q, p2p0)}
δ(q, a, p1) = {(q, p1p1)}	δ(q, b, p1) = {(q, ε)}
δ(q, a, p2) = {(q, ε)}	δ(q, b, p2) = {(q, p2p2)}
	δ(q, ε, p0) = {(q, ε)}

Этот автомат изображен на следующей схеме:

17. Постройте грамматику Ван-Вайнгаардена G, которая «вычисляет» фун­к­цию сложения, то есть должно выполняться L(G) = {1^m1ⁿ1^m+n │m, n ≥ 0}.

Решение. На основе соглашений об обозначениях в данном пособии (все встречающиеся большие буквы есть метапонятия в V_m, все встречаю­щиеся маленькие буквы и специальные знаки есть синтаксические знаки в V_z или терминальные символы в , S обозначается через start) доста­точно для грамматики Ван-Вайнгаардена G = {V_z, V_m, , R, P, S} указать только множество метапродукций R и множество схем продукций P.

Грамматика Ван-Вайнгаардена, которая вычисляет функцию сложения, определена заданием R и P в нормальной форме Бэкуса.

R:			P:
	A:: = 1A│ε		 start:: =  A1 A2 A1 plus A2
	A1:: = 1 A1│ε		 A1 plus A2:: =  A1  A2
	A2:: = 1 A2│ε		1A:: = 1A
			ε:: = ε

В качестве примера рассмотрим следующий вывод:

 start  1³1²1³ plus 1² ^*1³1²1³ 1² ^*1³1²1⁵

17. Постройте грамматику Ван-Вайнгаардена G, которая «вычисляет» функ­цию умножения, то есть должно выполняться L(G)={1^m1ⁿ1^m*n │m, n ≥ 0}.

Решение. Грамматика Ван-Вайнгаардена, которая вычисляет функцию умножения, определена заданием R и P в нормальной форме Бэкуса.

R:			P:
	A:: = 1A│ε		 start:: =  A1 A2 A1 mal A2
	A1:: = 1 A1│ε		 mal A2:: = ε
	A2:: = 1 A2│ε		 1 A1 mal A2:: =  A1 mal A2  A2
			1A:: = 1A
			ε:: = ε

Для примера рассмотрим следующий вывод:

 start  1²1³1² mal 1³ ^*1²1³1²mal 1³ 1²1³1 mal 1³1³ 1²1³mal 1³ 1³ 1³ 1²1³1³ 1³^*1³1²1⁶.

20. Постройте грамматику Ван-Вайнгаардена G, которая вычисляет функ­цию f(n): = n², n, то есть должно выполняться: L(G) = {1ⁿ1^n²│n ≥ 0}. Решение. Грамматика Ван-Вайнгаардена, которая вычисляет функцию f, определена заданием R и P в нормальной форме Бэкуса:

R:			P:
	A:: = 1A│ε		 start:: =  A A quadrat
			 quadrat:: = ε
			 1A quadrat:: =  A quadrat  1AA
			1A:: = 1A
			ε:: = ε

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

 start  1³1³ quadrat ^* 1³1³ quadrat 1³1² quadrat 11²1²

1³1quadrat 111 11²1² 1³quadrat 1 111 11²1² 1³1 1³ 1⁵ ^*1³1⁹.

20. Постройте грамматику Ван-Вайнгаардена G, которая порождает язык L={aⁿbⁿcⁿ│n  }.

Решение. Грамматика Ван-Вайнгаардена G, которая порождает язык L, определена заданием R и P в нормальной форме Бэкуса:

R:		P:
	A:: = 1A│ε		 start:: = aAbAcA
			a1A:: = aaA	a:: = ε
			 b1A:: = bbA	b:: = ε
			c1A:: = ccA	c:: = ε

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

 start  a11 b11 c11  a a1 b11 c11  aa1bb1 c11

aa1bb1cc1^*aaabbbccc^*aabbcc.

Замечание. Изменение правила для переменной  start:

start:: = a  b  c 

даёт L = { │ n   } для фиксированных k_i, m_i.

20. Постройте грамматику Ван-Вайнгаардена G, которая порождает язык L = {aⁱbⁱ│i, j \0, НОД(i, j) = 1}.

Решение. Воспользуемся тем, что НОД(i, j) = НОД(i, j-i) для j  i ≥ 1, соотв. НОД(i, j) = НОД(i-j, j) для j  i ≥ 1 и НОД(1, k) = НОД(k, 1) = 1 для k≥1.

Грамматика Ван-Вайнгаардена, которая порождает язык L, определя­ется ниже заданием R и P в нормальной форме Бэкуса:

R:			P:
	A:: = 1A│1		 start:: =  A bA A НОД B
	B:: = 1B│1		 A НОД B1A:: =  A НОД B1 
	A1:: = 1A1│1		 A1B НОД B :: =  A1 НОД B 
	B1:: = 1B1│1		 1 НОД B:: = ε
	C:: = 1C│ε		 A НОД 1 :: = ε
	D:: = 1D│ε		 a1C:: = a aC	 a:: = ε
			 b1D:: = b bD	 b:: = ε

В качестве примера пусть задан следующий вывод:

start a111 b11 111 НОД 11 ^*aaab11 111 НОД 11

^* aaabb 111 НОД 11  aaabb 1 НОД 11 aaabb.

Предварительные замечания к машинам Тьюринга. Для решения следующих примеров мы применим модель машины Тьюринга, кото­рая по сравнению с моделью, обсуждаемой в главе 2, является не­сколько ограниченной, – так называемую машину Тьюринга, связанную направлением. Пусть T = (Q, , , , q₀, F) произвольная машина Тью­ринга. Если существует переход (.,.) = (q,., L) (соответственно (.,.) = (q, …, R)), то будем говорить, что q достигается путем пере­хода влево (соответственно вправо). Отсюда возможно тогда, что со­стояние q достигается при переходе влево или при некотором другом переходе вправо. Машина Тьюринга, связанная направлением, есть та­кая машина, для которой подобное невозможно: каждое состояние q достигается всегда либо только переходом влево, либо вправо. (Не­трудно показать, что для каждой машины Тьюринга можно построить эквивалентную машину Тьюринга, связанную направлением (т.е. вы­числяющую тот же набор функций, соответственно принимающую тот же самый язык.)

Преимущество машин Тьюринга, связанных направлением, состоит в том, что они (подобно конечным автоматам) позволяют графическое представление, которое обычно наглядней, чем простое табулирование функции перехода . При этом поступают следующим образом: каж­дому состоянию q соответствует узел, в который вписывается «L» или «R» в зависимости от того, достигается q всегда только переходом влево и соответственно только переходом вправо. Для каждого пере­хода (q, A) = (p, B, D), D{L, R} строят направленное ребро от узла q к узлу р, обозначаемое (А, В). Начальное состояние и конечные состоя­ния (если такие имеются) обозначаются подходящим образом (как в конечных автоматах).

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

Решение. T = (Q, , , , q₀, F), где Q = {q₀, q₁, q₂, q₃},  = {a},

Г = {a, 0, 1, e}, F = .

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

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

Графическое представление этой машины Тьюринга, связанной направ­ле­нием, выглядит следующим образом:

(Так как начальное состояние q₀ не достигается ни при каком переходе, для него не нужно вписывать никакого направления («L» или «R») или можно было бы взять на выбор «R» или «L».)

24. Постройте машину Тьюринга, которая вычисляет следующую функ­цию:

f: ({a}^*)²  {a}^*, f(aⁿ, a^m) = a^n+m, n, m  .

Решение. Простейшая машина Тьюринга, которая вычисляет f, есть Т = ({q}, {a}, {a, e}, , q, ), графическое представление которой за­дано в виде:

Поскольку  нигде не определена, то qaⁿea^m для всех n, m   есть конеч­ная конфигурация. Так как qaⁿea^m ^* qaⁿea^m (0 шагов), то Т останавлива­ется при любых входных словах (aⁿ, a^m)  {a}^*  {a}^* в конечной конфи­гурации qaⁿea^m. Поэтому для всех входных слов (aⁿ, a^m)  {a}^*  {a}^*:

f_{T, 2}(aⁿ, a^m) = h(aⁿea^m) = aⁿa^m = a^n+m = f(aⁿ, a^m).

Дополнительные замечания. Т вычисляет все функции f: ({a}^*)^k  {a}^*, f(, …, ) = , f_T, k(, …, ) = h(e, …, e) = … = .

Если терминальный алфавит {a} машины Т заменить произвольным алфавитом , то можно показать, что полученная таким путем машина Тьюринга вычисляет все k-местные «функции сцепления» f: (^*)^k  ^*, f(w₁, …, w_k) = w₁…w_k.

25. Постройте машину Тьюринга, которая вычисляет следующую функ­цию:

f: ({a}^*)²  {a}^*, f(aⁿ, a^m) = a^{n  m}, n, m  .

Решение. Следующая идея является отправным пунктом для построения.

При вводе (aⁿ, a^m) начальное содержимое ленты есть aⁿea^m. Машина стирает первую а в первой а-группе и записывает после а^m слово А^m (А – символ ленты). Таким путем образуется a^n-1ea^mA^m. Теперь снова самое первое а стирается и в конце слова дописывается А^m. Так образуется a^n‑2ea^mA^2m. Этот процесс продолжается до тех пор, пока «не израсходу­ется» первая а-группа. Тем самым образуется a^mA^nm. Напоследок все а стираются и все А заменяются на а, тем самым образуется a^nm = f(aⁿ, a^m). Машина Тьюринга, которая это реализует, есть T = ({0, 1, 2, 3, 4, 5, 6, 7}, {a}, {a, A, B, e}, , 0, ), где  задана следующим графом:

Наглядное значение состояний 0,…, 7 следующее:

0	…	Стереть первое а первой а-группы.
1	…	Идти вправо до второй а-группы.
2	…	Первый символ а, для которого не происхо­дит еще дописывание символов А, маркиро­вать через В.
3, 4	…	В самом конце дописывать символ А, идти влево до маркировки В; удалить ее (т. е. В за­менить снова на а); идти вправо в состоя­ние 2.
5, 6	…	Если для всех а второй группы был дописан сзади А, то опять искать начало первой а‑группы и перейти в начальное состояние.
7	…	Заменить а не е, А на а.

26. Постройте машину Тьюринга, которая вычисляет следующую функцию:

f: {a, b}^*  {a, b}^*, f(w) = w^R, w  {a, b}^*

(w^R обозначает зеркальное отражение w).

Решение. Следующая идея является отправным пунктом для построения.

Каждая буква входного слова w = c₁ … c_n, (c_i  {a, b}), за исключением последней, сдвигается на одну позицию вправо, последняя буква запи­сывается перед с₁ (т. е. на первоначальную позицию буквы с₁). Таким путем образуется c_nc₁ … c_n-1. Далее то же самое делается с c₁ … c_n-1 (при этом c_n остается на ленте без изменений). Таким образом, образуется c_n с_n-1c₁ … c_n-2. Этот процесс повторяется до тех пор, пока «не израсхо­дуется» входное слово. Так образуется c_nc_n-1 … c₁ = w^R. Приводимая ниже машина Тьюринга Т вычисляет w^R описанным способом: T = ({0, 1, 2, 3, 4}, {a, b}, {a, b, e}, , 0, ), где  задана следующим графом:

Наглядное значение состояний 0,…, 4 следующее:

0	…	Сдвинуть слово от позиции головки вправо: стереть первый символ и сделать отметки в состоянии (1 «пометить а», 2 «пометить b»).
1, 2	…	Каждый следующий знак заменить на поме­ченный и одновременно пометить; послед­ний знак не писать, а сделать отметку в со­стоянии (3 для а, 4 для b).
3, 4	…	Идти влево к началу сдвинутого слова и впи­сать туда последний символ; после этого – шаг вправо в начальное состояние. Процесс повторяется циклически.

27. Постройте машину Тьюринга, которая принимает следующий язык L:

L = {aⁿb²ⁿc³ⁿ | n  } (L  {a, b, c}^*).

Решение. Исходным пунктом для построения является следующая идея.

Записанное на ленте слово попеременно пробегается слева направо, при этом (в указанной последовательности) символ а заменяется на А, два b – на В, три с – на С. (Если после замещения а на А выясняется, что больше не имеется в наличии двух b, соответственно трех с, ма­шина останавливается, не принимая слово.) Как только не остается ни одного символа а, то процесс прерывается и проверяется, содержит ли оставшееся слово еще хоть один b или с. Лишь в том случае, если не содержит, машина останавливается в конечном состоянии.

T = ({0, 1, 2, 3, 4, 5, 6, 7, 8}, {a, b, c}, {a, b, c, A, B, C, e}, , 0, {8}),

где  задана следующим графом:

Наглядное значение состояний 0,…, 8 следующее:

0, 7, 8	…	Если  входное слово, то оно сразу принима­ется, т. е. переходят в конечное состояние 8 ( = а0b20c30). Если существует еще один символ а, то он заменяется на А и тем самым начинается выше описанный «пробег». Если больше не имеется ни одного а, то в состоя­нии 7 проверяется, имеются ли еще символы b или с, и если нет, то слово акцептируется.
1, 2	…	Заменить первые два b на В.
3, 4, 5	…	Заменить первые три с на С.
6	…	Идти налево к позиции после символа А, за­писанного последним.

28. Постройте машину Тьюринга, которая принимает следующий язык L:

L = {aⁿ | n  } (L  {a, b}^*).

Решение. Отправным пунктом для построения является следующая идея.

Для принимаемого языка L справедливо, что   L и что для всех n, m , aⁿ⁺¹b^m  L выполняется тогда и только тогда, когда aⁿb^m-2n-1  L (m = (n + 1)²  m – 2n – 1 = n²). Чтобы проверить, лежит ли входное слово в L, поступают следующим образом:  принимается сразу. Из входного слова вида aⁿ⁺¹b^m путем стирания первого символа а и последних 2n+1 символов b производится слово aⁿb^m-2n-1. Это слово рассматривается как новое входное слово, и описанный процесс повто­ряется. Если таким способом первоначальное входное слово сокраща­ется до , то оно принимается. Если символы b остаются лишними, или для процесса стирания символов b не достает, машина останавливается, не принимая слово.

T = ({0, 1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, {a, b, A, e}, , 0, {8}),

где  задана следующим графом:

Содержательное значение состояний 0,…, 8 следующее:

0	…	Если  входное слово, то оно сразу принима­ется. Если же входное слово начинается с а, то этот а стирается.
1, 2	…	Последний символ b стирается.
3 – 7	…	Для каждого а в начале слова стираются два b в конце. (Для этого, при необходимости, один символ а маркируется (а  А), ищется конец слова (4, 5), стираются два b (5, 6, 7), ищется маркировка А (7), маркировка опять удаляется (а  А) и производится шаг влево в состоянии 3, для того чтобы повторить процесс для следующего а.) После этого производится переход в начальное состояние и оставшееся слово рассматривается как но­вое входное слово.

29. Постройте машину Тьюринга, которая принимает следующий язык L:

L = {ww | w  {a, b}^*}.

Решение. Отправным пунктом для построения является следующая идея.

Сначала устанавливается, является ли длина входного слова – четной и одновременно буквы первой половины слова маркируются «одно­кратно» (а  а', b  b'), а второй половины слова «двукратно» (а  а'', b  b''). Если при этом выясняется, что длина входного слова нечетная, то машина останавливается, не принимая слово. В противном случае, при необходимости, первый однократно маркированный символ срав­нивается с первым двукратно маркированным символом. Если эти сим­волы совпадают (без учета маркировки), то первый заменяется на е, а последний – на Х. В противном случае машина останавливается, не ак­цептируя слово. Если таким способом удается получить слово, состоя­щее из одних символов Х, то переходят в конечное состояние.

T = ({0, 1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, {a, b, a', b', a'', b'', X, e}, , 0, {8}),

где  задана следующим графом:

Наглядное значение состояний 0,…, 8 следующее:

0, 1, 2, 3	…	 принимается сразу же. При вводе непус­того слова первая (вторая) половина этого слова маркируется однократно (двукратно).
4	…	Идти влево к первому е.
5, 6, 7	…	Стереть первый однократно маркированный символ и сделать отметку в состоянии (a'  6, b' 7). Идти вправо к первому дву­кратно маркированному символу, при совпа­дении заменить на Х и снова перейти в 4. Если на ленте стоят одни только символы Х, то слово принимается.