Счетчик автомат - Counter automaton

Схема счетного автомата. Каждая ячейка его стека содержит либо "А"или пробел.

В Информатика, в частности в теории формальные языки, а счетчик автомат, или же счетчик машина, это выталкивающий автомат всего с двумя символами, ${displaystyle A}$ и начальный символ в ${displaystyle Gamma}$ , конечный набор символов стека.^[1]^:171

Эквивалентно счетчик автомат - это недетерминированный конечный автомат с дополнительной ячейкой памяти, которая может содержать одно неотрицательное целое число (неограниченного размера), которое можно увеличивать, уменьшать и проверять на равенство нулю.^[2]^:351

Характеристики

Класс счетных автоматов может распознать собственное надмножество обычный^{[примечание 1]} и подмножество детерминированные контекстно-свободные языки.^[2]^:352

Например, язык ${displaystyle {a ^ {n} b ^ {n}: nin mathbb {N}}}$ нерегулярный^{[заметка 2]} язык, принятый автоматом счетчика: он может использовать символ ${displaystyle A}$ подсчитать количество ${displaystyle a}$ s в заданной строке ввода ${displaystyle x}$ (написание ${displaystyle A}$ для каждого ${displaystyle a}$ в ${displaystyle x}$ ), после этого он может удалить ${displaystyle A}$ для каждого ${displaystyle b}$ в ${displaystyle x}$ .

Автомат с двумя счетчиками, то есть двухступенчатая машина Тьюринга с двухсимвольным алфавитом, может моделировать произвольный Машина Тьюринга.^[1]^:172

Примечания

^ Каждый обычный язык L принимается некоторыми конечный автомат F (видеть Регулярный язык # Эквивалентные формализмы ). Обогащение F со стеком из двух символов, который игнорируется FКонтроль делает его автоматом счетчика, принимающим L.
^ посредством лемма о накачке для регулярных языков

Счетчик автомат - Counter automaton

Характеристики

Примечания

Рекомендации