Счетчиковый автомат

Материал из WEGA
Версия от 13:23, 2 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Счетчиковый автомат''' (''Counter automation'') - модификация ''машин Минского'', связа...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Счетчиковый автомат (Counter automation) - модификация машин Минского, связанная с расширением их лентой и операторами двух типов: оператора печати символа на ленту и оператора недетерминированного перехода. Если автомат достигает заключительной вершины, он останавливается, и результатом его работы является напечатанное им слово на ленте. Если автомат зацикливается при любом возможном варианте выполнения его программы, то он порождает пустой язык. Известно, что любой рекурсивно перечислимый язык может быть порожден некоторым С.а..

Литература

[Котов]