ماشین امگا

ماشین امگا ($\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_{0}a_{1}a_{2}a_{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_{0}a_{1}a_{2}a_{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 \exists 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$ آمده باشد.

مثال

یک ماشین قطعی بوخی

در اینجا مثالی از ماشین امگای قطعی بوخی آورده‌ایم. توصیف این ماشین به صورت مقابل است:

• $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$ آمده باشد.