Autômato com fila

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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).[1]

Turing completude[editar | editar código-fonte]


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. [2] A prova formal é frequentemente um exercício de teórica nos cursos de ciências da computação.

Aplicações[editar | editar código-fonte]

Máquinas de fila oferecem um modelo simples sobre a base de arquitetura de computadores, [3] [4] linguagens de programação ou algoritmos. [5] [6]

Referências

  1. Kozen, Dexter C.. In: David Gries, Fred B. Schneider. Automata and Computability. 1 ed. New York: Springer-Verlag, 1997. 368–370 pp. ISBN 0-387-94907-0
  2. Rus, Teodor. Variants of Turing Machines Lecture Notes Covering Theory of Computation. University of Iowa, Iowa City, IA, 52242-1419. Página visitada em 2007-11-06.
  3. Feller, M.; M.D. Ercegovac. (1981). "Queue machines: An organization for parallel computation". Lecture Notes in Computer Science 111: 37. DOI:10.1007/BFb0105108.
  4. Schmit, Herman; Benjamin Levine, Benjamin Ylvisaker. (2002). "Queue Machines: Hardware Compilation in Hardware". 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'02): 152. DOI:10.1109/FPGA.2002.1106670.
  5. Moore, Christopher (1999-09-20). Queues, Stacks, and Transcendentality at the Transition to Chaos Algorithms Project's Seminar. INRIA. Página visitada em 2007-11-06.
  6. von Thum, Manfred (2007). A queue machine for evaluating expressions LaTrobe University. Página visitada em 2007-11-06.

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

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