نظریه مک‌ناتون کیست؟ توضیح بده.
در نظریه اتوماتا نظریه مک‌ناتون اشاره دارد به قضیه‌ای که بیان می‌دارد مجموعه‌ای از زبان‌های ω-منظم برابر خواهد بود با مجموعه‌ای که توسط ماشین مولر قطعی تشخیص داده شود. برای اثبات این قضیه الگوریتمی ارائه می‌شود که در آن برای هر زبان ω-منظم یک ماشین مولر قطعی ساخته می‌شود و بالعکس.این قضیه نتایج مهم و متعددی دارد. از آنجایی که ماشین بوچی و زبان‌های ω-منظم هر دو بیانی از یکدیگر هستند، این قضیه این نتیجه را می‌رساند که ماشین بوچی و ماشین قطعی مولر به‌طور مساوی بیانگر یکدیگر هستند.بیان اصلی قضیه.در مقاله اصلی مک‌ناتون، قضیه بدین صورت بیان شده‌است که:" یک ω-رویداد منظم است اگر و فقط اگر حالت متناهی باشد."امروزه از عبارت ω-زبان‌ها به جای ω-رویدادها استفاده می‌شود. همچنین طبق تعریف مک‌ناتون یک ω-رویداد، یک رویداد حالت متناهی است اگر یک ماشین مولر قطعی وجود داشته باشد که آن را تشخیص دهد.ساختن یک زبان ω-منظم از یک ماشین مولر قطعی.اثبات یک طرف این قضیه بدین صورت است که نشان داده می‌شود هر ماشین مولر داده شده یک زبان ω-منظم را تشخیص می‌دهد.فرض کنید ("A" = (Q,Σ,δ,q0,F یک ماشین قطعی مولر باشد. اتحاد تعداد زیاد و معینی از زبان‌های ω-منظم، یک زبان ω-منظم را تولید می‌کند، لذا بدون کم شدن از کلیت مساله می‌توان فرض نمود که شرط قبولی مولر F دقیقاً شامل یک مجموعه از حالت‌های {q1...,qn} می‌شود. فرض می‌شود که α یک زبان منظم باشد که عناصرش "A" را از q0 تا q1 دربر بگیرد. برای هر i از 1 تا βi ،n یک زبان منظمی باشد که عناصرش "A" را از qi تا q(i mod n)+1 را بدون عبور از هر وضعیتی خارج از {q1...,qn} در بر بگیرند. ادعا می‌شود که α(β1...βn)ω یک زبان ω-منظم است که توسط ماشین مولر A تشخیص داده می‌شود.ساختن یک ماشین مولر قطعی از یک زبان ω-منظم داده شده.سمت دیگر قضیه را بدین طریق می‌توان اثبات کرد که به ازای هر زبان ω-منظم داده شده یک ماشین مولر وجود دارد که آن را تشخیص بدهد.اتحاد تعداد متناهی و زیادی از ماشین‌های قطعی مولر به سادگی قابل ساخت است، لذا بدون کم شدن از کلیت مساله، فرض می‌شود که زبان ω-منظم داده شده به شکل αβω است. همچنین فرض شود که ω-کلمه w=a1,a2... ∈ αβω. "w"(i,j یک بخش معین شامل ai+1...,aj-1,aj از w در نظر گرفته می‌شود. برای ساختن ماشین مولر مرتبط با αβω، دو مفهموم در رابطه با w معرفی می‌شود.خدمت زمان j در خدمت زمان i است اگر j &gt; i و "*w"(0,i) ∈ αβ و "*w"(i,j) ∈ β.هم‌ارزی با "ارزیابی" در زمان i، k "هم‌ارز" است با j اگر *i,j≤k "w"(0,j) ∈ αβ*، "w"(0,i) ∈ αβ، و برای هر کلمه x در "*w"(i,k)x ∈ β*، Σ، اگر و فقط اگر "*w"(j,k)x ∈ β یا به عبارتی "(E(i,j,k". به سادگی می‌توان توجه کرد که اگر "(E(i,j,k" آنگاه برای همه k &lt;l داریم "(E(i,j,l". به عبارت دیگر، اگر چنانچه i و j هم‌ارز ارزیابی شوند، در آن صورت از آن به بعد هم‌ارز خواهند ماند. همچنین برای مقدار l مشابه، l به i خدمت می‌کند اگر و فقط اگر l به j خدمت کند. قرار می‌دهیم "(E(i,j" اگر یک k وجود داشته باشد که (E(i,j,k.فرض کنید که p تعداد وضعیت‌ها در کمترین ماشین متناهی معین Aβ* باشد که زبان *β را تشخیص می‌دهد. اکنون به بیان دو لم دربارهٔ دو مفهوم بالا می‌پردازیم.لم 1برای هر زمانی چون k، در میان زمان‌های i و j که i,j&lt;k به طوریکه (w(0,i و (*w(0,j ∈ αβ و تعداد هم‌ارزی‌های ایجاد شده توسط (E(i,j,k به وسیله p متناهی شده‌است.لم 2"W" ∈ αβω اگر و فقط اگر زمانی چون i وجود داشته باشد که به تعداد نامتناهی زمان هم‌ارز با i باشد که به i خدمت کند.ساختن ماشین مولر.هر دو مفهموم "خدمت کردن" و "هم‌ارزی" در لم 2 مورد استفاده قرار گرفته‌است. اکنون از این لم برای ساختن یک ماشین مولر برای زبان αβω استفاده می‌کنیم. ماشین پیشنهادی یک کلمه را قبول می‌کند اگر و فقط اگر زمان i وجود داشته باشد که سمت راست لم 2 را ارضا گرداند. ماشین مذکور در ادامه توصیف شده‌است. توجه شود که این ماشین، یک ماشین قطعی مولر خواهد بود.این ماشین شامل p+2 ماشین متناهی قطعی و یک کنترل‌کننده مستر باشد که p سایز Aβ* می‌باشد. یکی از p+2 ماشین قادر است تا *αβ را تشخیص دهد و این ماشین در هر چرخه ورودی می‌گیرد. در هر زمان i یا کنترل‌کننده مستر ارتباط برقرار می‌کند، خواه "*w"(0,i) ∈ αβ برقرار باشد و یا خیر. باقی این p+1 ماشین کپی‌هایی از Aβ* هستند. مستر می‌تواند یک ماشین Aβ* را فعال یا غیر فعال گرداند. اگر مستر آن را غیرفعال گرداند، آنگاه آن در حالت ابتدایی خود باقی مانده و نسبت به ورودی‌ها بی‌توجه خواهد شد. اگر مستر آن را فعال گرداند، سپس آن ماشین داده را خوانده و حرکت می‌کند تا زمانی که مستر آن را غیرفعال گردانیده و وادار به بازگشت به حالت ابتدایی کند. مستر قادر است تا یک ماشین Aβ* را به تعداد دفعاتی که مایل است فعال و غیرفعال گرداند. مستر در هر لحظه اطلاعات زیر را دربارهٔ ماشین‌های Aβ* ذخیره می‌کند.برای خروجی، مستر یک جفت چراغ سبز و قرمز را برای هر ماشین Aβ* داراست.اگر یک ماشین به حالت غیرفعال برود، چراغ قرمز روشن می‌شود. چراغ سبز ماشین M که در زمان j فعال شده‌است در دو حالت زیر در زمان i روشن خواهد بود:لم 4برعکس، اگر ماشین Aβ* مانند M وجود داشته باشد که چراغ سبزش بینهایت بار روشن شده بوده باشد و چراغ قرمزش تنها دفعات متناهی زده باشد، آنگاه زمان‌های نامتناهی وجود خواهد داشت که هم‌ارز بوده و به آخرین زمانی که ماشین M فعال شده‌است، خدمت می‌کند.لم 5"w ∈ αβω اگر و فقط اگر برای برخی ماشین‌های Aβ* چراغ سبز تعداد دفعات نامتناهی فلاش زده و چراغ قرمز تنها دفعات متناهی فلاش می‌زند.توصیف بالا از یک ماشین کامل می‌تواند به عنوان یک ماشین قطعی گسترده در نظر گرفته شود. اکنون باید شرط پذیرش مولر تعریف گردد. در این ماشین گسترده، μn را مجموعه حالت‌های مرتبط با ماشین nام از نوع Aβ* تعریف می‌کنیم که در آن چراغ سبز فلاش زده و چراغ قرمز فلاش نمی‌زند. فرض کنید νn مجموعه حالت‌هایی باشد که در آن چراغ قرمز مربوط ماشین nام فلاش نمی‌زند. در نتیجه، شرط پذیرش مولر خواهد بود: این شرط، ساخت ماشین مولر مورد نظر را به اتمام می‌رساند.