ماشین امگا

ماشین امگا ( ω − automaton {\displaystyle \omega -{\textbf {automaton}}} )(انگلیسی: Omega-Automaton) گونه ای از ماشین حالات متناهی است که ورودی آن رشته های نامتناهی به جای رشته های متناهی می باشد. از آنجایی که رشته های ورودی نامتناهی می باشند، ماشین های امگا به جای مجموعه وضعیت های قبول، شرایط قبول دارند.نبو
با توجه به ورودی ماشین های امگا که نامتناهی است، می توان از آن ها برای توصیف وضعیت سامانه هایی از قبیل سخت افزارها، سیستم های عامل، سیستم های کنترلی، تصدیق سیستم ها و محاسبات استفاده کرد.
ماشین های امگا همانند ماشین های حالت متناهی به دو گونهٔ قطعی و غیرقطعی تقسیم می شوند. انواع گوناگون ماشین های امگا عبارتند از: ماشین بوخی، ماشین رابین، ماشین زوجیت، ماشین مولر و … تمامی این ماشین ها به هر دو صورت قطعی و غیرقطعی وجود دارند و تفاوت آن ها در شرایط قبولی می باشد. به غیر از ماشین بوخی قطعی که از تمامی مدل های دیگر ضعیف تر است، تمامی این مدل ها زبان های منظم امگا را تشخیص می دهند.
مجموعه اعداد صحیح نامنفی را با ω {\displaystyle \omega }   نشان می دهیم، یعنی ω = { 0 , 1 , 2 , . . . } {\displaystyle \omega =\{0,1,2,...\}}  . الفبای ورودی متناهی را نیز با Σ {\displaystyle \Sigma }   نمایش می دهیم. در حالی که Σ ∗ {\displaystyle \Sigma ^{*}}   مجموعهٔ تمام کلمات متناهی بر روی الفبای Σ {\displaystyle \Sigma }   است، Σ ω {\displaystyle \Sigma ^{\omega }}   مجموعهٔ تمام کلمات نامتناهی بر روی الفبای مذکور می باشد. زبان L {\displaystyle L}   را یک ω {\displaystyle \omega }  -زبان گوییم هرگاه کلمات آن زیرمجموعه ای از Σ ∗ {\displaystyle \Sigma ^{*}}   باشند، یعنی L ⊆ Σ ω {\displaystyle L\subseteq \Sigma ^{\omega }}  .