2dca (двусторонние детерминированные автоматы с одним счетчиком) (Petersen, 1994) могут распознавать следующий унарный язык: POWER={02n∣n≥0}.POWER={02n∣n≥0}.\begin{equation} \mathtt{POWER} = \lbrace 0^{2^n} \mid n \geq 0 \rbrace. \end{equation} Есть ли другой нетривиальный унарный язык,...
Можно стандартно два счетчика ( ) машина со следующими инструкциями: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 выбрать следующий язык: L={n2∣n≥1}L={n2∣n≥1}L = \{ n^2 \mid n \geq 1 \}...
Односторонние чередующиеся нажимные автоматы (1APDA) могут распознавать любой язык в (Чередование, Чандра, Козен и Стокмейер, 1981) . Заменив хранилище 1APDA со счетчиком, можно получить односторонний чередующийся автомат с одним счетчиком (1ACA). Мой вопрос о 1ACA на унарных языках.Д ТяMЕ( 2O ( n...