Магазинний автомат (МА)

Дата додавання: 2014-11-28; переглядів: 921.

Такий автомат має обмежений набір операцій зі стрічкою, а саме:

1. Дописати символ в кінці робочої зони, і пересунутись вправо.

2. Пересунутись вліво, і витерти символ під голівкою (замінити на λ).

За допомогою автомата з двома магазинами можна промоделювати роботу машини Тьюрінга.

Магазин з унарним алфавітом називається лічильником. Два лічильники можуть промоделювати роботу магазину.

Стековий автомат (СА)

Аналогічний МА, але крім цього вміє читати символи з середини стрічки.

<== попередня лекція	\|	наступна лекція ==>
Переваги і недоліки	\|	Операції автомата