Počítadlo automat - Counter automaton

Schéma počítadla automatu. Každá buňka zásobníku obsahuje buď „A"nebo mezerník.

v počítačová věda, konkrétněji v teorii formální jazyky, a počítadlo automatnebo pultový stroj, je zasunovací automat pouze se dvěma symboly, ${displaystyle A}$ a počáteční symbol v ${displaystyle Gamma}$, konečná sada symbolů zásobníku.^[1]:171

Ekvivalentně je počítadlový automat a nedeterministický konečný automat s další paměťovou buňkou, která pojme jedno nezáporné celé číslo (neomezené velikosti), které lze zvýšit, snížit nebo otestovat na nulu.^[2]:351

Vlastnosti

Třída automatů počítadel dokáže rozpoznat vlastní nadmnožinu pravidelný^{[poznámka 1]} a podmnožina jazyky bez deterministického kontextu.^[2]:352

Například jazyk ${displaystyle {a ^ {n} b ^ {n}: nin mathbb {N}}}$ je nepravidelný^{[poznámka 2]} jazyk akceptovaný automatem počítadla: Může používat symbol ${displaystyle A}$ spočítat počet ${displaystyle a}$s v daném vstupním řetězci ${displaystyle x}$ (psaní ${displaystyle A}$ pro každého ${displaystyle a}$ v ${displaystyle x}$), poté může odstranit ${displaystyle A}$ pro každého ${displaystyle b}$ v ${displaystyle x}$.

Automat se dvěma počitadly, tj dvouvrstvý Turingův stroj s abecedou se dvěma symboly může simulovat libovolný Turingův stroj.^[1]:172

Poznámky

Reference