Pytania oznaczone «counter-automata»

2dca (dwukierunkowe deterministyczne automaty licznikowe) (Petersen, 1994) może rozpoznać następujący jednoargumentowy język: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Czy jest jakiś inny nietrywialny, unary język...

Czy standardowa maszyna z dwoma licznikami ( ) może następujące instrukcje:c1,c2c1,c2c_1,c_2 1) ADD 1 to c_i, GOTO label_j 2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k 3) GOTO label_j 4) HALT and ACCEPT|REJECT wybierz następujący język: L={n2∣n≥1}L={n2∣n≥1}L = \{ n^2 \mid...

Jednokierunkowe naprzemienne automaty wypychające (1APDA) mogą rozpoznać dowolny język w (Alternacja autorstwa Chandra, Kozen i Stockmeyer, 1981) . Zastępując przechowywanie w dół 1APDA przez licznik, możemy uzyskać jednokierunkowy automat na przemian z jednym licznikiem (1ACA). Moje pytanie...