Autômato com fila

Uma máquina com fila ou autômato com fila é uma máquina de estado finito com a habilidade de armazenar e recuperar dados a partir de uma fila de memória infinita. É um modelo de computação equivalente a uma máquina de Turing, e, portanto, ele pode processar qualquer linguagem formal.

Teoria

Definimos uma máquina com fila por uma 6-tuplas.

$M=(Q,\Sigma ,\Gamma ,\$,q,\delta )$ , onde:

• $\,Q$ é um conjunto finito de estados;
• $\,\Sigma$ é um conjunto finito de alfabeto de entrada;
• $\,\Gamma$ é um conjunto finito de alfabeto de fila;
• $\,\$\in \Gamma -\Sigma$ é o símbolo inicial de fila;
• $\,q\in Q$ é o estado inicial;
• $\,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}$ é a função de transição.

Nós definimos o estado atual da máquina por uma configuração, um par ordenado de estados e conteúdo da fila $\,(q,\gamma )\in Q\times \Gamma ^{*}$(note que $\,\Gamma ^{*}$ define o fecho de Kleene ou subconjuntos do conjunto $\,\Gamma$). Portanto, a configuração inicial sobre uma cadeia de entrada $\,x$ é definida como $\,(s,x\$)$, e podemos definir nossa transição como a função que, dado um estado inicial e uma fila, assume a função para um novo estado e fila. Observe a propriedade da fila em que "o primeiro que entra é o primeiro que sai" na relação

$\,(p,A\alpha )\rightarrow _{M}^{1}(q,\alpha \gamma )$

em que $\,\rightarrow _{M}^{1}$ define a próxima configuração, ou simplesmente a função de transição da configuração atual para a próxima.

A máquina aceita uma cadeia $\,x\in \Sigma ^{*}$ se depois de um número (possivelmente infinito) de transições a configuração inicial evolui para esgotar a cadeia (atingindo uma cadeia nula $\,\epsilon$) ou $\,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon ).$

Turing completude

Podemos provar que uma máquina de fila é equivalente a uma máquina de Turing, mostrando que uma máquina de fila pode simular uma máquina de Turing e vice-versa.

Uma máquina de Turing pode ser simulada por uma máquina de fila que mantém uma cópia do conteúdo da máquina de Turing na sua fila em todos os momentos, com dois marcadores especiais: um para a posição da cabeça da MT e um para a extremidade da fita; suas transições simulam as da MT passando pela fila inteira, colocando fora cada um de seus símbolos e recolocando outro símbolo no lugar ou perto da posição da cabeça, o equivalente ao efeito da transição de uma MT.

Uma máquina de fila pode ser simulada por uma máquina de Turing, porém mais facilmente por uma máquina de Turing multifita, que é conhecida por ser equivalente a uma máquina de fita única normal. A simulação de uma máquina de fila lê a entrada em uma fita e armazena a fila na segunda, lendo e removendo dependendo da definição das transições simples para os símbolos de início e fim da fita. A prova formal é frequentemente um exercício de teórica nos cursos de ciências da computação.

Aplicações

Máquinas de fila oferecem um modelo simples sobre a base de arquitetura de computadores, linguagens de programação ou algoritmos.

Ver também

• Computabilidade
• Autômatos finitos determinísticos
• Autômato com pilha

Ligações externas

• Manufactoria, um jogo multi-tarefa de browser em flash com a implementação de vários algoritmos usando um modelo de máquina fila.