ماشین امگا ( ω − automaton ) ( انگلیسی: Omega - Automaton ) گونه ای از ماشین حالات متناهی است که ورودی آن رشته های نامتناهی به جای رشته های متناهی می باشد. از آنجایی که رشته های ورودی نامتناهی می باشند، ماشین های امگا به جای مجموعه وضعیت های قبول، شرایط قبول دارند.
با توجه به ورودی ماشین های امگا که نامتناهی است، می توان از آن ها برای توصیف وضعیت سامانه هایی از قبیل سخت افزارها، سیستم های عامل، سیستم های کنترلی، تصدیق سیستم ها و محاسبات استفاده کرد. [ ۱]
ماشین های امگا همانند ماشین های حالت متناهی به دو گونهٔ قطعی و غیرقطعی تقسیم می شوند. انواع گوناگون ماشین های امگا عبارتند از: ماشین بوخی، ماشین رابین، ماشین زوجیت، ماشین مولر و … تمامی این ماشین ها به هر دو صورت قطعی و غیرقطعی وجود دارند و تفاوت آن ها در شرایط قبولی می باشد. به غیر از ماشین بوخی قطعی که از تمامی مدل های دیگر ضعیف تر است، تمامی این مدل ها زبان های منظم امگا را تشخیص می دهند. [ ۱]
مجموعه اعداد صحیح نامنفی را با ω نشان می دهیم، یعنی ω = { 0 , 1 , 2 , . . . } . الفبای ورودی متناهی را نیز با Σ نمایش می دهیم. در حالی که Σ ∗ مجموعهٔ تمام کلمات متناهی بر روی الفبای Σ است، Σ ω مجموعهٔ تمام کلمات نامتناهی بر روی الفبای مذکور می باشد. زبان L را یک ω - زبان گوییم هرگاه کلمات آن زیرمجموعه ای از Σ ∗ باشند، یعنی L ⊆ Σ ω . [ ۲]
یک ماشین امگا قطعی A یک چندتایی به صورت A = ( Q , Σ , δ , Q 0 , A c c ) است. در ادامه به تبیین هر کدام از مؤلفه ها می پردازیم:
• Q {\displaystyle Q} مجموعه ای متناهی است که وضعیت های ماشین امگا را نشان می دهد.
• Σ {\displaystyle \Sigma } مجموعه ای متناهی است که الفبای ماشین امگا را نشان می دهد.
• δ : Q × Σ → Q {\displaystyle \delta :Q\times \Sigma \rightarrow Q} تابع انتقال ماشین امگا است.
• Q 0 ∈ Q {\displaystyle Q_{0}\in Q} وضعیت اولیه ماشین است.
• A c c {\displaystyle Acc} شرایط قابل قبول را نشان می دهد که به صورت خاص A c c ⊆ Q ω {\displaystyle Acc\subseteq Q^{\omega }} است.
• یک ورودی به ماشین قطعی A {\displaystyle A} مثل α {\displaystyle \alpha } به صورت رشته ای نامتناهی α = a 0 a 1 a 2 a 3 . . . ∈ Σ ω {\displaystyle \alpha =a_{0}a_{1}a_{2}a_{3}. . . \in \Sigma ^{\omega }} است. اجرای A {\displaystyle A} بر روی α {\displaystyle \alpha } برابر با دنباله ای نامتناهی از وضعیت ها مثل s {\displaystyle s} و به صورت مقابل است:
• s 0 = Q 0 {\displaystyle s_{0}=Q_{0}}
• ∀ i ≥ 1 s i = δ ( s i − 1 , a i − 1 ) {\displaystyle \forall i\geq 1\quad s_{i}=\delta ( s_{i - 1}, a_{i - 1} ) }
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبا توجه به ورودی ماشین های امگا که نامتناهی است، می توان از آن ها برای توصیف وضعیت سامانه هایی از قبیل سخت افزارها، سیستم های عامل، سیستم های کنترلی، تصدیق سیستم ها و محاسبات استفاده کرد. [ ۱]
ماشین های امگا همانند ماشین های حالت متناهی به دو گونهٔ قطعی و غیرقطعی تقسیم می شوند. انواع گوناگون ماشین های امگا عبارتند از: ماشین بوخی، ماشین رابین، ماشین زوجیت، ماشین مولر و … تمامی این ماشین ها به هر دو صورت قطعی و غیرقطعی وجود دارند و تفاوت آن ها در شرایط قبولی می باشد. به غیر از ماشین بوخی قطعی که از تمامی مدل های دیگر ضعیف تر است، تمامی این مدل ها زبان های منظم امگا را تشخیص می دهند. [ ۱]
مجموعه اعداد صحیح نامنفی را با ω نشان می دهیم، یعنی ω = { 0 , 1 , 2 , . . . } . الفبای ورودی متناهی را نیز با Σ نمایش می دهیم. در حالی که Σ ∗ مجموعهٔ تمام کلمات متناهی بر روی الفبای Σ است، Σ ω مجموعهٔ تمام کلمات نامتناهی بر روی الفبای مذکور می باشد. زبان L را یک ω - زبان گوییم هرگاه کلمات آن زیرمجموعه ای از Σ ∗ باشند، یعنی L ⊆ Σ ω . [ ۲]
یک ماشین امگا قطعی A یک چندتایی به صورت A = ( Q , Σ , δ , Q 0 , A c c ) است. در ادامه به تبیین هر کدام از مؤلفه ها می پردازیم:
• Q {\displaystyle Q} مجموعه ای متناهی است که وضعیت های ماشین امگا را نشان می دهد.
• Σ {\displaystyle \Sigma } مجموعه ای متناهی است که الفبای ماشین امگا را نشان می دهد.
• δ : Q × Σ → Q {\displaystyle \delta :Q\times \Sigma \rightarrow Q} تابع انتقال ماشین امگا است.
• Q 0 ∈ Q {\displaystyle Q_{0}\in Q} وضعیت اولیه ماشین است.
• A c c {\displaystyle Acc} شرایط قابل قبول را نشان می دهد که به صورت خاص A c c ⊆ Q ω {\displaystyle Acc\subseteq Q^{\omega }} است.
• یک ورودی به ماشین قطعی A {\displaystyle A} مثل α {\displaystyle \alpha } به صورت رشته ای نامتناهی α = a 0 a 1 a 2 a 3 . . . ∈ Σ ω {\displaystyle \alpha =a_{0}a_{1}a_{2}a_{3}. . . \in \Sigma ^{\omega }} است. اجرای A {\displaystyle A} بر روی α {\displaystyle \alpha } برابر با دنباله ای نامتناهی از وضعیت ها مثل s {\displaystyle s} و به صورت مقابل است:
• s 0 = Q 0 {\displaystyle s_{0}=Q_{0}}
• ∀ i ≥ 1 s i = δ ( s i − 1 , a i − 1 ) {\displaystyle \forall i\geq 1\quad s_{i}=\delta ( s_{i - 1}, a_{i - 1} ) }
wiki: ماشین امگا