ماشین امگا
ماشین امگا (formula_1)(انگلیسی: Omega-Automaton) گونه‌ای از ماشین حالات متناهی است که ورودی آن رشته‌های نامتناهی به جای رشته‌های متناهی می‌باشد. از آنجایی که رشته‌های ورودی نامتناهی می‌باشند، ماشین‌های امگا به جای مجموعه وضعیت‌های قبول، شرایط قبول دارند.
با توجه به ورودی ماشین‌های امگا که نامتناهی است، می‌توان از آن‌ها برای توصیف وضعیت سامانه‌هایی از قبیل سخت‌افزارها، سیستم‌های عامل، سیستم‌های کنترلی، تصدیق سیستم‌ها و محاسبات استفاده کرد.
ماشین‌های امگا همانند ماشین‌های حالت متناهی به دو گونهٔ قطعی و غیرقطعی تقسیم می‌شوند. انواع گوناگون ماشین‌های امگا عبارتند از: ماشین بوخی، ماشین رابین، ماشین زوجیت، ماشین مولر و … تمامی این ماشین‌ها به هر دو صورت قطعی و غیرقطعی وجود دارند و تفاوت آن‌ها در شرایط قبولی می‌باشد. به غیر از ماشین بوخی قطعی که از تمامی مدل‌های دیگر ضعیف‌تر است، تمامی این مدل‌ها زبان‌های منظم امگا را تشخیص می‌دهند.
مجموعه اعداد صحیح نامنفی را با formula_2 نشان می‌دهیم، یعنی formula_3. الفبای ورودی متناهی را نیز با formula_4 نمایش می‌دهیم. در حالی که formula_5 مجموعهٔ تمام کلمات متناهی بر روی الفبای formula_4 است، formula_7 مجموعهٔ تمام کلمات نامتناهی بر روی الفبای مذکور می‌باشد. زبان formula_8 را یک formula_2-زبان گوییم هرگاه کلمات آن زیرمجموعه‌ای از formula_5 باشند، یعنی formula_11.
یک ماشین امگا قطعی formula_12 یک چندتایی به صورت formula_13 است. در ادامه به تبیین هر کدام از مؤلفه‌ها می‌پردازیم:
یک ماشین امگا غیرقطعی formula_12 یک چندتایی به صورت formula_29 است. در ادامه به تبیین هر کدام از مؤلفه‌ها می‌پردازیم: در اینجا بر خلاف ماشین امگا قطعی برای انتقال بین وضعیت‌های مختلف به جای یک تابع از یک رابطه استفاده می‌کنیم. در این حالت وضعیت بعدی لزوماً به صورت یکتا تعیین نمی‌شود بلکه می‌تواند حالات گوناگونی داشته باشد و به صورت غیرقطعی وارد تمامی آن‌ها می‌شود. یک ورودی به ماشین غیرقطعی formula_12 مثل formula_21 به صورت رشته‌ای نامتناهی formula_22 است. اجرای formula_12 بر روی formula_21 برابر با دنباله‌ای نامتناهی از وضعیت‌ها مثل formula_25 و به صورت مقابل است:
در ماشین‌های حالات متناهی، اجرای هر ماشین بر روی رشتهٔ ورودی در یک وضعیت خاص پایان می‌یابد و بنا بر آنکه آن وضعیت عضوی از مجموعه وضعیت‌های قابل قبول باشد، رشته ورودی تأیید یا رد می‌شود. در ماشین‌های امگا، بر خلاف ماشین‌های حالت متناهی، باید به اجرای ماشین بر روی رشته توجه کرد و با توجه به وضعیت‌هایی که اجرا به خود می‌بیند تصمیم به تأیید یا رد رشته گرفت. یک رشته دلخواه مورد قبول ماشین قرار می‌گیرد هرگاه خروجی وضعیت‌های اجرای مربوط به آن درون formula_18 باشد. زبان ماشین امگای formula_12 برابر است با تمامی کلماتی که توسط این ماشین قبول می‌شوند و با formula_47 نشان داده می‌شود. برای هر اجرا مانند formula_25 مجموعهٔ formula_49 را برابر با وضعیت‌هایی از ماشین در نظر می‌گیریم که هر کدام نامتناهی بار در اجرا ظاهر می‌شوند، یعنی formula_50. حال با استفاده از این تعریف به بیان انواع گوناگون ماشین‌های امگا می‌پردازیم.
در این ماشین مجموعه formula_18 برابر با زیرمجموعه‌ای از وضعیت‌ها مانند formula_52 است و در آن اجرای formula_25 قبول می‌شود هرگاه شرط formula_54 برقرار باشد. به تعبیری دیگر یک وضعیت مورد قبول باشد که در اجرای formula_25 بینهایت بار ظاهر شود.
در این ماشین مجموعه formula_18 برابر است با formula_57. در این ماشین اجراهایی مورد قبول واقع می‌شوند که در آن‌ها عضوی از formula_58 مانند formula_59 وجود داشته باشد که formula_60 و formula_61.
در این ماشین مجموعه وضعیت‌ها را به صورت formula_62 در نظر می‌گیریم و شرط قبول شدن اجرای formula_25 آن است که formula_64.
در این ماشین مجموعه formula_18 برابر با زیرمجموعه‌ای از مجموعه توانی وضعیت‌ها مانند formula_66 است و در آن اجرای formula_25 قبول می‌شود هرگاه شرط formula_68 برقرار باشد. به تعبیری دیگر تمام وضعیت‌هایی که بینهایت بار تکرار می‌شوند مجموعه‌ای را تشکیل دهند که در formula_69 آمده باشد.
در اینجا مثالی از ماشین امگای قطعی بوخی آورده‌ایم. توصیف این ماشین به صورت مقابل است: زبان این ماشین برابر است با تمام کلمات امگایی که در آن‌ها بینهایت بار حرف formula_78 آمده باشد. حال اگر داشته باشیم formula_79 آنگاه زبان ماشین برابر است با تمام کلمات امگایی که در آن‌ها بینهایت بار حرف formula_80 آمده باشد.