Quais idiomas são reconhecidos por máquinas de balcão único?

As máquinas de balcão com dois ou mais contadores geralmente são equivalentes às máquinas de Turing em cursos sobre a teoria da computação. No entanto, eu não vi uma análise formal de quais idiomas podem ser reconhecidos por uma máquina de balcão único. Essas linguagens são equivalentes às linguagens livres de contexto (talvez por alguma construção inteligente que as relacione aos PDAs), ou são uma classe de linguagens totalmente diferente?

Um autômato de um contador é um autómato pushdown, com apenas um símbolo permitido na pilha (mais um símbolo de fundo fixo). Os idiomas reconhecidos por um autômato de contador formam um subconjunto apropriado dos idiomas livres de contexto.

Por exemplo, um autômato de 1 contador pode reconhecer o idioma que não é regular, mas não pode reconhecer o idioma { a n b m a m b n } que é livre de contexto e pode ser reconhecido por um contador 2 autômatos também.$\{a^nb^n\}$$\{a^nb^ma^mb^n\}$

Se k-DCA é um autômato de contador k determinístico e k-NCA é um autómato de contador k não determinístico, temos as seguintes inclusões apropriadas:

DFA (idiomas regulares) 1-DCA ⊂ 2-DCA$\subset$$\subset$

1-DCA 1-NCA$\subset$

Se não permitir que transições (alternar para tempo real ), então k-DCA ⊂ K '-DCA para k <k'.$\epsilon$$\subset$

Apenas para conclusão: existem idiomas sem contexto, mas que não podem ser reconhecidos por autômatos de contador (k-DCA com k 2) (por exemplo { w w R } ), e idiomas reconhecidos por autômatos de contador que não são livres de contexto (por exemplo { a n b n c n } ). Um autômato de contador (em particular um autômato de dois contadores) pode ser Turing completo somente se suas entradas e saídas forem codificadas corretamente (consulte a entrada da Wikipedia para obter detalhes).$\geq$$\{ww^R\}$$\{a^nb^nc^n\}$

Os autómatos contrários foram muito estudados no passado da linguagem formal antiga, no contexto da teoria AFA e AFL (famílias abstratas de autômatos e línguas) por equipes dos EUA e da França (Ginsberg, Greibach, ..., Nivat, Berstel, ...)

Os autômatos de contador são normalmente definidos como autômatos de estado finito equipados com memória externa, consistindo em um número natural (ou vários, se você tiver mais de um contador). Esse número pode ser incrementado, decrementado e (geralmente) testado para zero. Uma computação começa com zero e só é aceita quando o contador é zero no final, comparável à aceitação da pilha vazia do pushdown.

Se uma máquina desse tipo tiver pelo menos dois desses contadores, será equivalente a uma máquina de Turing, mesmo no caso determinístico. A prova desse fato é de Minsky e pode ser encontrada no artigo da wikipedia que você vinculou. Obviamente, o modelo está relacionado à máquina de registro mencionada na mesma página da Wikipedia. Os problemas de codificação mencionados no artigo da wikipedia não são importantes nesta configuração aqui, pois consideramos os autômatos com uma fita de entrada (afinal precisamos ler uma string de entrada) enquanto a wikipedia nesta página assume apenas contadores.

Esse contador de autômatos pode ser visto como um tipo especial de pda, com apenas um símbolo de pilha e um fundo da pilha (que nunca é movido). Isso permite que o autômato teste se o contador / pilha é zero e age de acordo.

De fato, existem três tipos de autômatos contrários. Então, combine os resultados com sabedoria ou você acabará com contradições (como aconteceu comigo no passado). Todos os três tipos são (estritamente) incluídos nas linguagens sem contexto para um contador.

O tipo acima armazena um número inteiro (ou um número natural, que não importa) e pode testar seu conteúdo como zero. O autómato de contador cego armazena um número inteiro, mas não pode testar o zero. Eles podem contar expictly abaixo de zero. Autômatos de contador parcialmente cegos não podem testar o zero, mas armazenam um número natural. Se a máquina tentar ficar abaixo de zero, ela pára sem aceitar. Esse é um tipo de armazenamento natural para modelar redes de Petri. Ele também é ralado para o PDA, agora com um único símbolo de pilha sem o marcador especial inferior (e, portanto, o problema de testar o zero: ficamos presos ao exibir o último elemento da pilha). Às vezes, os nomes das famílias definidas pelos modelos de contador respetivo são OCL, ROCL e 1-BLIND.

Todas essas famílias foram estudadas, todas são (mas eu estou enferrujado na minha teoria da AFA / AFL) principais trios completos (= cones racionais), o que significa que elas são fechadas sob morfismos (inversos) e interseção com linguagens regulares e podem ser obtidas usando essas operações começando com um único idioma. Para a maior família OCL (com teste zero), você pode começar com o idioma$(Dc)^*$ Onde $D = \{ w\in \{a,b\}^* \mid \#_a(w) = \#_b(w) \}$é a "linguagem Dyck frente e verso ligada entre parênteses" (na terminologia apropriada ao assunto). Existe uma intuição importante relacionada a esse idioma. Símbolos$a$ e $b$ refletir estalando e empurrando, $c$ é o teste zero.

Como exemplo de pesquisa relevante, a Latteux et al. Têm um artigo não trivial "A família das línguas de balcão único é fechada sob quociente" (que na verdade é sobre ROCL).