. متن داده‌شده را خلاصه کن

متن: در مقاله اصلی مک‌ناتون، قضیه بدین صورت بیان شده‌است که: «یک ω-رویداد منظم است اگر و فقط اگر حالت متناهی باشد.» امروزه از عبارت ω-زبان‌ها به جای ω-رویدادها استفاده می‌شود. همچنین طبق تعریف مک‌ناتون یک ω-رویداد، یک رویداد حالت متناهی است اگر یک ماشین مولر قطعی وجود داشته باشد که آن را تشخیص دهد. اثبات یک‌طرف این قضیه بدین صورت است که نشان داده می‌شود هر ماشین مولر داده‌شده یک‌زبان ω-منظم را تشخیص می‌دهد. فرض کنید (a = (q,σ,δ,q ۰ ,f یک ماشین قطعی مولر باشد. اتحاد تعداد زیاد و معینی از زبان‌های ω-منظم، یک‌زبان ω-منظم را تولید می‌کند، لذا بدون کم شدن از کلیت مساله می‌توان فرض نمود که شرط قبولی مولر f دقیقا شامل یک مجموعه از حالت‌های {q ۱ , …,qn} می‌شود. فرض می‌شود که α یک‌زبان منظم باشد که عناصرش a را از q ۰ تا q ۱ دربر بگیرد. برای هر i از ۱ تا βi، n یک‌زبان منظمی باشد که عناصرش a را از qi تا q (i mod n) + ۱ را بدون عبور از هر وضعیتی خارج از {q ۱ , …,qn} در بر بگیرند. ادعا می‌شود که α (β ۱ …βn) ω یک‌زبان ω-منظم است که توسط ماشین مولر a تشخیص داده می‌شود. سمت دیگر قضیه را بدین طریق می‌توان اثبات کرد که به ازای هر زبان ω-منظم داده‌شده یک ماشین مولر وجود دارد که آن را تشخیص بدهد. اتحاد تعداد متناهی و زیادی از ماشین‌های قطعی مولر به سادگی قابل ساخت است، لذا بدون کم شدن از کلیت مساله، فرض می‌شود که زبان ω-منظم داده‌شده به شکل αβω است. همچنین فرض شود که ω-کلمه w=a ۱ ,a ۲ , … ∈ αβω. w (i,j یک بخش معین شامل ai+ ۱ , …,aj- ۱ ,aj از w در نظر گرفته می‌شود. برای ساختن ماشین مولر مرتبط با αβω، دو مفهموم در رابطه با w معرفی می‌شود. خدمت (به انگلیسی: favor) زمان j در خدمت زمان i است اگر j > i و *w (۰ ,i) ∈ αβ و *w (i,j) ∈ β. هم‌ارزی (به انگلیسی: equivalence) با ارزیابی در زمان i، k هم‌ارز است با j اگر *i,j≤k w (۰ ,j) ∈ αβ*، w (۰ ,i) ∈ αβ، و برای هر کلمه x در *w (i,k) x ∈ β*، σ، اگر و فقط اگر *w (j,k) x ∈ β یا به عبارتی (e (i,j,k. به سادگی می‌توان توجه کرد که اگر (e (i,j,k آنگاه برای همه k <l داریم (e (i,j,l. به عبارت دیگر، اگر چنانچه i و j هم‌ارز ارزیابی شوند، در آن صورت از آن به بعد هم‌ارز خواهند ماند. همچنین برای مقدار l مشابه، l به i خدمت می‌کند اگر و فقط اگر l به j خدمت کند. اکنون به بیان دو لم درباره دو …
خلاصه:
در نظریه اتوماتا (به انگلیسی : automata theory) نظریه مک‌ناتون (به انگلیسی : mcnaughton's theorem) اشاره دارد به قضیه‌ای که بیان می‌دارد مجموعه‌ای از زبان‌های ω-منظم برابر خواهد بود با مجموعه‌ای که توسط ماشین مولر (به انگلیسی : muller automata) قطعی تشخیص داده شود . برای اثبات این قضیه الگوریتمی ارائه می‌شود که در آن برای هر زبان ω-منظم یک ماشین مولر قطعی ساخته می‌شود و بالعکس.این قضیه نتایج مهم و متعددی دارد . از آنجایی که ماشین بوچی (به انگلیسی : büchi automaton) و زبان‌های ω-منظم هر دو بیانی از یکدیگر هستند ، این قضیه این نتیجه را می‌رساند که ماشین بوچی و ماشین قطعی مولر به‌طور مساوی بیانگر یکدیگر هستند .