Automat fronty - Queue automaton

A fronta stroj nebo automat fronty je konečný stavový stroj se schopností ukládat a načítat data z nekonečné paměti fronta. Jedná se o model výpočtu ekvivalentní a Turingův stroj, a proto může zpracovávat stejnou třídu formální jazyky.

Teorie

Stroj ve frontě lze definovat jako šestici

${ displaystyle M = (Q, Sigma, Gamma, $, s, delta)}$ kde

• ${ displaystyle , Q}$ je konečná sada státy;
• ${ displaystyle , Sigma podmnožina Gamma}$ je konečná množina vstupní abeceda;
• ${ displaystyle , gama}$ je konečný abeceda fronty;
• ${ displaystyle , $ v Gamma - Sigma}$ je symbol počáteční fronty;
• ${ displaystyle , s v Q}$ je počáteční stav;
• ${ displaystyle , delta: Q times Gamma rightarrow Q times Gamma ^ {*}}$ je přechodová funkce.

Stroj konfigurace je uspořádaná dvojice obsahu jejího stavu a fronty ${ displaystyle , (q, gamma) v Q krát Gamma ^ {*}}$, kde ${ displaystyle , Gamma ^ {*}}$ označuje Kleene uzavření z ${ displaystyle , gama}$. Počáteční konfigurace na vstupním řetězci ${ displaystyle , x}$ je definován jako ${ displaystyle , (s, x $)}$a přechod ${ displaystyle rightarrow _ {M} ^ {1}}$ z jedné konfigurace do druhé je definována jako:

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

kde ${ displaystyle A}$ je symbol z abecedy fronty, ${ displaystyle alpha}$ je posloupnost symbolů fronty (${ displaystyle alpha in gama ^ {*}}$), a ${ displaystyle (q, gamma) = delta (p, A)}$. Všimněte si vlastnosti „first-in-first-out“ fronty v relaci.

Zařízení přijímá řetězec ${ displaystyle , x in Sigma ^ {*}}$ pokud se po konečném počtu přechodů vyvíjí počáteční konfigurace k vyčerpání řetězce (dosažení nulového řetězce ${ displaystyle , epsilon}$), nebo ${ displaystyle , (s, x $) rightarrow _ {M} ^ {*} (q, epsilon).}$^[1]

Turingova úplnost

Můžeme dokázat, že stroj ve frontě je ekvivalentní s Turingovým strojem, když ukážeme, že stroj ve frontě může simulovat Turingův stroj a naopak.

Turingův stroj může být simulován strojem ve frontě, který po celou dobu uchovává kopii obsahu Turingova stroje ve své frontě, se dvěma speciálními značkami: jeden pro pozici hlavy TM a jeden pro konec pásky; jeho přechody simulují přechod TM tím, že procházejí celou frontou, vyskočí z každého z jeho symbolů a znovu označí buď vyskočený symbol, nebo v blízkosti polohy hlavy ekvivalent efektu přechodu TM.

Frontu lze simulovat pomocí Turingova stroje, ale snadněji pomocí a vícepásmový Turingův stroj, o kterém je známo, že je ekvivalentní normálnímu jednopáskovému stroji. Simulační stroj fronty čte vstup na jednu pásku a ukládá frontu na druhou s pushy a popy definovanými jednoduchými přechody k počátečním a koncovým symbolům pásky.^[2] Formálním důkazem toho je často cvičení v kurzech teoretické informatiky.

Aplikace

Fronty nabízejí jednoduchý model, na kterém lze založit počítačové architektury,^[3][4] programovací jazyky nebo algoritmy.^[5][6]

Viz také

• Vyčíslitelnost
• Turingovy ekvivalenty
• Deterministický konečný automat
• Pushdown automat
• Systém značek
• Manufactoria, flashová hra v prohlížeči, která má hráče za úkol implementovat různé algoritmy pomocí modelu stroje ve frontě.

Reference