Considere uma máquina de estados finitos como de costume, mas a cada transição, ela também pode atualizar um contador inteiro adicionando ou subtraindo um número. Digamos que uma função de transição da forma se mova para o novo estado p e adicione k ao contador, onde k ∈ Z (para que k possa ser positivo, negativo ou zero) .
Uma string será aceita se o estado final e o valor do contador estiverem em , onde F é um conjunto finito de pares de estados e valores de contador.
Este modelo é conhecido? Não encontrei nenhuma referência a essa extensão específica.
finite-automata
Chao Xu
fonte
fonte
Respostas:
Assumindo que pode ser qualquer número inteiro, isso pode ser formalizado como um autômato cego de um contador . Geralmente estes autómatos aceitar em estado final quando seu contador é zero, mas podemos facilmente modelar o seu tipo de aceitação, se você permitir £ transições (que não consomem entrada). Se não me engano, como nos autômatos de estados finitos, é possível se livrar do ϵ , mas esse é um resultado não trivial.k ϵ ϵ
Existem vários tipos de autômatos de balcão. Na forma mais geral, eles podem testar se o valor do contador é igual a zero. Os idiomas que eles aceitam são um subconjunto estrito dos idiomas sem contexto.
O modelo que você provavelmente está procurando é chamado de cego ; ele não pode testar para zero, exceto como o teste final para aceitação no final do cálculo.
fonte
Este modelo é uma variante de autômatos ponderados, que são amplamente estudados (embora existam muitas perguntas em aberto sobre eles). Você pode começar aqui: Manual de autômatos ponderados .
Observe que às vezes eles são chamados de "autômatos à distância" (embora isso esteja se tornando menos comum).
fonte