ماشین امگا

**ماشین امگا** (\omega-\textbf{automaton})(انگلیسی: Omega-Automaton) گونه‌ای از ماشین حالات متناهی است که ورودی آن رشته‌های نامتناهی به جای رشته‌های متناهی می‌باشد. از آنجایی که رشته‌های ورودی نامتناهی می‌باشند، ماشین‌های امگا به جای مجموعه وضعیت‌های قبول، شرایط قبول دارند.

با توجه به ورودی ماشین‌های امگا که نامتناهی است، می‌توان از آن‌ها برای توصیف وضعیت سامانه‌هایی از قبیل سخت‌افزارها، سیستم‌های عامل، سیستم‌های کنترلی، تصدیق سیستم‌ها و محاسبات استفاده کرد.

ماشین‌های امگا همانند ماشین‌های حالت متناهی به دو گونهٔ قطعی و غیرقطعی تقسیم می‌شوند. انواع گوناگون ماشین‌های امگا عبارتند از: ماشین بوخی، ماشین رابین، ماشین زوجیت، ماشین مولر و … تمامی این ماشین‌ها به هر دو صورت قطعی و غیرقطعی وجود دارند و تفاوت آن‌ها در شرایط قبولی می‌باشد. به غیر از ماشین بوخی قطعی که از تمامی مدل‌های دیگر ضعیف‌تر است، تمامی این مدل‌ها زبان‌های منظم امگا را تشخیص می‌دهند.

## معرفی و مقدمه
مجموعه اعداد صحیح نامنفی را با \omega نشان می‌دهیم، یعنی \omega = \{0, 1, 2, ... \}. الفبای ورودی متناهی را نیز با \Sigma نمایش می‌دهیم. در حالی که \Sigma^* مجموعهٔ تمام کلمات متناهی بر روی الفبای \Sigma است، \Sigma^\omega مجموعهٔ تمام کلمات نامتناهی بر روی الفبای مذکور می‌باشد. زبان L را یک \omega-زبان گوییم هرگاه کلمات آن زیرمجموعه‌ای از \Sigma^* باشند، یعنی L \subseteq \Sigma^\omega.

## ماشین امگا قطعی
یک ماشین امگا قطعی A یک چندتایی به صورت A = (Q, \Sigma, \delta, Q_0, Acc) است. در ادامه به تبیین هر کدام از مؤلفه‌ها می‌پردازیم:
* Q مجموعه‌ای متناهی است که وضعیت‌های ماشین امگا را نشان می‌دهد.
* \Sigma مجموعه‌ای متناهی است که الفبای ماشین امگا را نشان می‌دهد.
* \delta : Q \times \Sigma \rightarrow Q تابع انتقال ماشین امگا است.
* Q_0 \in Q وضعیت اولیه ماشین است.
* Acc شرایط قابل قبول را نشان می‌دهد که به صورت خاص Acc \subseteq Q^\omega است.
* یک ورودی به ماشین قطعی A مثل \alpha به صورت رشته‌ای نامتناهی \alpha = a_0a_1a_2a_3... \in \Sigma^\omega است. اجرای A بر روی \alpha برابر با دنباله‌ای نامتناهی از وضعیت‌ها مثل s و به صورت مقابل است:
* s_0 =  Q_0
* \forall i \geq 1 \quad s_i = \delta(s_{i-1}, a_{i-1})

## ماشین امگا غیرقطعی
یک ماشین امگا غیرقطعی A یک چندتایی به صورت A = (Q, \Sigma, \triangle, Q_0, Acc) است. در ادامه به تبیین هر کدام از مؤلفه‌ها می‌پردازیم:
* Q مجموعه‌ای متناهی است که وضعیت‌های ماشین امگا را نشان می‌دهد.
* \Sigma مجموعه‌ای متناهی است که الفبای ماشین امگا را نشان می‌دهد.
* \triangle زیرمجموعه‌ای از Q \times \Sigma \times Q است و رابطه انتقال ماشین امگا نام دارد.
* Q_0 \subseteq Q وضعیت اولیه ماشین است.
* Acc شرایط قابل قبول را نشان می‌دهد که به صورت خاص Acc \subseteq Q^\omega است.
در اینجا بر خلاف ماشین امگا قطعی برای انتقال بین وضعیت‌های مختلف به جای یک تابع از یک رابطه استفاده می‌کنیم. در این حالت وضعیت بعدی لزوماً به صورت یکتا تعیین نمی‌شود بلکه می‌تواند حالات گوناگونی داشته باشد و به صورت غیرقطعی وارد تمامی آن‌ها می‌شود. یک ورودی به ماشین غیرقطعی A مثل \alpha به صورت رشته‌ای نامتناهی \alpha = a_0a_1a_2a_3... \in \Sigma^\omega است. اجرای A بر روی \alpha برابر با دنباله‌ای نامتناهی از وضعیت‌ها مثل s و به صورت مقابل است:
* s_0 \in Q_0
* \forall i \geq 1 \quad s_i \in \triangle(s_{i-1}, a_{i-1})

## شرایط قبول
در ماشین‌های حالات متناهی، اجرای هر ماشین بر روی رشتهٔ ورودی در یک وضعیت خاص پایان می‌یابد و بنا بر آنکه آن وضعیت عضوی از مجموعه وضعیت‌های قابل قبول باشد، رشته ورودی تأیید یا رد می‌شود. در ماشین‌های امگا، بر خلاف ماشین‌های حالت متناهی، باید به اجرای ماشین بر روی رشته توجه کرد و با توجه به وضعیت‌هایی که اجرا به خود می‌بیند تصمیم به تأیید یا رد رشته گرفت. یک رشته دلخواه مورد قبول ماشین قرار می‌گیرد هرگاه خروجی وضعیت‌های اجرای مربوط به آن درون Acc باشد. زبان ماشین امگای A برابر است با تمامی کلماتی که توسط این ماشین قبول می‌شوند و با L(A) نشان داده می‌شود. برای هر اجرا مانند s مجموعهٔ Inf(s) را برابر با وضعیت‌هایی از ماشین در نظر می‌گیریم که هر کدام نامتناهی بار در اجرا ظاهر می‌شوند، یعنی Inf(s) = \{q \in Q | \forall i \geq 0 \quad \exist j \geq i : s_j = q\}. حال با استفاده از این تعریف به بیان انواع گوناگون ماشین‌های امگا می‌پردازیم.

### ماشین بوخی
در این ماشین مجموعه Acc برابر با زیرمجموعه‌ای از وضعیت‌ها مانند F \subseteq Q است و در آن اجرای s قبول می‌شود هرگاه شرط Inf(s) \cap F \neq \emptyset برقرار باشد. به تعبیری دیگر یک وضعیت مورد قبول باشد که در اجرای s بینهایت بار ظاهر شود.

### ماشین رابین
در این ماشین مجموعه Acc برابر است با \Omega = \{(E_i, F_i) | E_i, F_i \subseteq Q \}. در این ماشین اجراهایی مورد قبول واقع می‌شوند که در آن‌ها عضوی از \Omega مانند (E_i, F_i) وجود داشته باشد که Inf(s) \cap E_i = \emptyset و Inf(s) \cap F_i \neq \emptyset.

### ماشین زوجیت
در این ماشین مجموعه وضعیت‌ها را به صورت Q = \{0, 1, ..., k\} در نظر می‌گیریم و شرط قبول شدن اجرای s آن است که \min{Inf(s)} \bmod 2 = 0.

### ماشین مولر
در این ماشین مجموعه Acc برابر با زیرمجموعه‌ای از مجموعه توانی وضعیت‌ها مانند F \subseteq P(Q) است و در آن اجرای s قبول می‌شود هرگاه شرط Inf(s) \in F برقرار باشد. به تعبیری دیگر تمام وضعیت‌هایی که بینهایت بار تکرار می‌شوند مجموعه‌ای را تشکیل دهند که در F آمده باشد.

## مثال
[پیوند=[پرونده:S Automata.jpg|جایگزین=مثالی از ماشین قطعی بوخی|بندانگشتی|یک ماشین قطعی بوخی]]
در اینجا مثالی از ماشین امگای قطعی بوخی آورده‌ایم. توصیف این ماشین به صورت مقابل است:
* Q = \{q_1, q_2\}
* \Sigma = \{a, b\}
* \delta(q_1, a) = a، \delta(q_1, b) = q_2، \delta(q_2, a) = q_1 و \delta(q_2, b) = q_2
* Q_0 = q_1
* Acc = \{q_1\}
زبان این ماشین برابر است با تمام کلمات امگایی که در آن‌ها بینهایت بار حرف a آمده باشد. حال اگر داشته باشیم Acc = \{q_2\} آنگاه زبان ماشین برابر است با تمام کلمات امگایی که در آن‌ها بینهایت بار حرف b آمده باشد.

## منابع

رده:ماشین متناهی