Легко бачити, що автомат

<{A, B, e}, {a₀, a₁, a₂, a₃}, {d₀ , A, e}, f₃ , a₀, d₀ ,a₃>

допускає слова мови L спустошенням магазину. Розглянемо його роботу, наприклад, над словами ААВВ, ВВ, АВА:

а) (а₀, АABB, d₀ )| (а₁, АBB, Ad₀ )| (а₀, BB, d₀ )| (а₂, B, d₀ )| (а₃, e, e ).

Оскільки (а₃, e, e ) - заключна конфігурація, то слово ААВВ допускається автоматом;

б) (а₀, BB, d₀ )| (а₂, B, d₀ )| (а₃, e, e ).

Таким чином, слово ВВ є допустимим;

в) (а₀, АBA, d₀ )| (а₁, BA, Ad₀ )| (а₂, A, d₀ ).

Далі автомат не може виконати жодного такту відповідно f₃ , а конфігурація (а₂, A, d₀ ) не є заключною.

Отже, слово АВА не є допустимим,

Можна задати автомат з магазинною пам’яттю, який допускає таку ж мову із спустошенням магазину, причому буде мати менше станів. Цей автомат з магазинною пам’яттю має такий вигляд:

<{A, B, e}, {a₀, a₁, a₂}, {d₀ , e}, f₃ , a₀, d₀ ,a₂>

f₃(a₀, A,d₀ )= (a₀, d₀)

f₃(a₁, B,d₀ )= (a₂, e)

f₃(a₀, B,d₀ )= (a₁, d₀).

Автомат з магазинною пам’яттю, що допускає таку ж мову без спустошення магазину,

<{A, B, e}, {a₀, a₁, a₂}, {d₀ , A, e}, f₃ , a₀, d₀ ,a₂>,

де

f₃(a₀, A,d₀ )= (a₀, Ad₀); f₃(a₀, A, A )= (a₀, AA);

f₃(a₀, B, d₀ )= (a₁, d₀); f₃(a₀, B,A )= (a₁, A);

f₃(a₁, B, d₀ )= (a₂, e); f₃(a₁, B,A )= (a₂, e).

Наприклад, працюючи з словом ААВВ

(а₀, АABB, d₀ )| (а₀, АBB, Ad₀ )| (а₀, BB, d₀ )| (а₁, B, AAd₀ )| (а₂, e, Ad₀).

автомат перейде до заключної конфігурації, не спустошуючи магазин.

На прикладі автомату з магазинною пам’яттю

<{A, B, e}, {a₀, a₁}, {d₀ , B, e}, f₃ , a₀, d₀ ,a₁>,

де

f₃(a₀, A,d₀ )= (a₀, d₀); f₃(a₀, B, d₀ )= (a₀, B);

f₃(a₀, B, B )= (a₁, e),

що допускає таку ж мову L , можна побачити цікавий зв’язок автоматів з магазинною пам’яттю та скінчених автоматів.

Мова L допускається кінцевим автоматом, заданим таким графом переходів:

якщо a₀ - початковий, a а₂ - заключний стани.

Очевидно, у графі переходів без стану a₁ між станами a₀ та . не обійтися. У той же час у МП-автоматі станів тільки два, тому що роль стану а₂. грає символ В у магазині. Більше того, у МП-автоматі можна, використовуючи магазин, зменшити кількість станів до одного, якщо вимагати, щоб ланцюжки допускалися спустошенням магазину:

<{A, B, e}, {a₀}, {d₀ , B, e}, f₃ , a₀, d₀ ,a₀>,

де

f₃(a₀, A,d₀ )= (a₀, d₀); f₃(a₀, B, B)= (a₀, e); f₃(a₀, B, d₀ )= (a₀, B).

Вправа І2. Задати схему дій лінійно-обмеженого автомату, що допускає в алфавіті {А, Б, В} мову з вправи 27 теми 4.1.

Вправа 13. Задати схему дій лінійно-обмеженого автомату, що допускає у алфавіті {А, Б, В} мови з вправи 28 теми 4.1.

Вправа 14. Описати роботу машини Т’юрінга, заданої такою таблицею дій:

Стан	В клітинці, що розглядається	В клітинці, що розглядається
	a/
1	CO	EL2
2	R3	EL2
3	PO	CO
	б/
1	CO	R2
2	R3	CO
3	PL4	CO
4	L5	CO
5	L5	EL5

Вправа 15. Чи можна побудувати лінійно-обмежений автомат, результатом роботи якого над словом, що подає число a , буде слово, що подає число а+1.

Вправа 16. Задати таблицю дій машини Тьюрінга, що допускає тільки ланцюжки мови з вправи 36 теми 4.1.