ماشین صف

ماشین صف (به انگلیسی: queue machine)یک ماشین حالت متناهی است که توانایی ذخیره و بازیابی اطلاعات را از یک صف با حافظه بی نهایت دارد. این یک مدل محاسباتی معادل ماشین تورینگ است و بنابراین می تواند همان کلاس زبان رسمی را پردازش کند.
Q {\displaystyle \,Q}   مجوعه حالات متناهی
Σ ⊂ Γ {\displaystyle \,\Sigma \subset \Gamma }   مجموعه متناهی الفبای ورودی
Γ {\displaystyle \,\Gamma }   صف محدود الفبا
$ ∈ Γ − Σ {\displaystyle \,\$\in \Gamma -\Sigma }   نماد اولیه صف است.
s ∈ Q {\displaystyle \,s\in Q}   حالت شروع
δ : Q × Γ → Q × Γ ∗ {\displaystyle \,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}}   تابع انتقال
یک ماشین صف با شش تایی زیر تعریف می شود:
یک پیکر بندی ماشین، به صورت دوتایی حالت و محتوای صف است و به صورت ( q , γ ) ∈ Q × Γ ∗ {\displaystyle \,(q,\gamma )\in Q\times \Gamma ^{*}}   نشان داده می شود، که Γ ∗ {\displaystyle \,\Gamma ^{*}}   به معنای ستاره کلین Γ {\displaystyle \,\Gamma }   می باشد. پیکربندی شروع با رشته ورودی x {\displaystyle \,x}   به صورت ( s , x $ ) {\displaystyle \,(s,x\$)}   تعریف می شود و انتقال → M 1 {\displaystyle \rightarrow _{M}^{1}}   از یک پیکربندی به پیکربندی بعدی به صورت زیر بیان می شود:
که A {\displaystyle A}   نشانه ای از صف الفبا، α {\displaystyle \alpha }   یک دنباله از نمادهای صف( α ∈ Γ ∗ {\displaystyle \alpha \in \Gamma ^{*}}  )، و ( q , γ ) = δ ( p , A ) {\displaystyle (q,\gamma )=\delta (p,A)}  . توجه داشته باشید که ویژگی "first-in-first-out" از صف در رابطه وجود دارد.