카운터 오토매틱

카운터 자동화의 다이어그램.스택의 각 셀은 "A" 또는 공간 기호를 포함한다.

컴퓨터 과학에서, 공식 언어 이론, 카운터 오토매틱 또는 카운터 머신에서 더 특별한 것은 푸시다운 오토매틱으로, $A{\displaystyle }$ ${\$$displaystyle A}$와 $\gamma {\displaystyle \mathrm{}}$ $\{\backslash$$displaystyle \Gamma}$의 초기 기호는 스택 기호의 유한 집합이다.^{[1]: 171}

마찬가지로 카운터오토마톤은 비 음수 정수(무제한 크기) 1개를 담을 수 있는 추가 메모리 셀을 가진 비계수적 유한 자동화로, 증가, 감소, 0으로 시험할 수 있다.^{[2]: 351}

특성.

카운터 오토마타 클래스는 정규 언어의^{[note 1]} 적절한 상위 집합과 결정론적 컨텍스트 자유 언어의 하위 집합을 인식할 수 있다.^{[2]: 352}

예를 들어${\displaystyle }${${\displaystyle n}$ ${\displaystyle {}^{}{}^{}}$ n : ${\displaystyle n\mathbb{}}$} N } ${\displaystyle \{a^{n^{$n}^{$n}}:n\in \mathb{N}$\}}}}}은 카운터$$ 자동화에 의해 허용되는 비정규^{[note 2]} 언어다.기호 $A{\displaystyle }$ ${\displaystyle$ $A$$}$을(를$)$ 사용하여$$ 지정된 입력 $문자열{\displaystyle }$ x ${\displaystyle x}($$x$$${\$displaystyle$$$x}에서 각$${\$displaystyle$ a}에$$ $대해{\displaystyle }$ ${\$displaystystyle $A$$}$의 수를 계산할 수 있으며,$$$$ 그 후 각 $b{\displaystyle }$ ${\displaystate$ A$}$을($으$)에 대해 A ${\$discopy)할 수 있다.$yle b}$ $in$ x ${\displaystyle$ x$\}.$

2-카운터 오토메이션, 즉 2-스택 튜링 기계와 2-심볼 알파벳을 가진 2-스택 튜링 기계는 임의 튜링 기계를 시뮬레이션할 수 있다.^{[1]: 172}

메모들

참조