Счетчиковый автомат: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Счетчиковый автомат''' (''Counter automation'') - модификация ''машин Минского'', связа...) |
KVN (обсуждение | вклад) Метка: визуальный редактор отключён |
||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
'''Счетчиковый автомат''' (''Counter | '''Счетчиковый автомат''' (''[[Counter automaton]]'') — | ||
модификация ''машин Минского'', связанная с расширением их | модификация ''[[машина Минского|машин Минского]]'', связанная с расширением их | ||
лентой и операторами двух типов: оператора печати символа | лентой и операторами двух типов: оператора печати символа | ||
на ленту и | на ленту и | ||
оператора недетерминированного перехода. | оператора недетерминированного перехода. | ||
Если автомат достигает заключительной вершины, он | Если автомат достигает заключительной [[вершина|вершины]], он | ||
останавливается, и результатом его работы является | останавливается, и результатом его работы является | ||
напечатанное им слово на ленте. Если автомат зацикливается | напечатанное им слово на ленте. Если автомат зацикливается | ||
при любом возможном варианте выполнения его программы, то он | при любом возможном варианте выполнения его программы, то он | ||
порождает пустой язык. Известно, что любой рекурсивно | порождает пустой язык. Известно, что любой рекурсивно | ||
перечислимый язык может быть порожден некоторым ''' | перечислимый язык может быть порожден некоторым '''счетчиковым автоматом''' . | ||
==Литература== | ==Литература== | ||
[ | * Котов В.Е. Сети Петри. — М.: Наука, 1984. | ||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009 | |||
[[Категория:Теория автоматов]] | |||
Текущая версия от 19:57, 7 ноября 2024
Счетчиковый автомат (Counter automaton) — модификация машин Минского, связанная с расширением их лентой и операторами двух типов: оператора печати символа на ленту и оператора недетерминированного перехода. Если автомат достигает заключительной вершины, он останавливается, и результатом его работы является напечатанное им слово на ленте. Если автомат зацикливается при любом возможном варианте выполнения его программы, то он порождает пустой язык. Известно, что любой рекурсивно перечислимый язык может быть порожден некоторым счетчиковым автоматом .
Литература
- Котов В.Е. Сети Петри. — М.: Наука, 1984.
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009