قضیه مای‌هیل–نرود

از ویکی‌پدیا، دانشنامهٔ آزاد

در قضیه زبان صوری قضیه مای‌هیل–نرود (به انگلیسی: Myhill–Nerode theorem) یک شرط لازم و کافی را برای منظم شدن زبان فراهم می‌کند. این قضیه به اسم جان مای‌هیل و آنیل نرود که آن را در دانشگاه شیکاگو ثابت نموده‌اند نام‌گذاری شده‌است.(Nerode 1958)

بیانیه‌ای از قضیه[ویرایش]

زبان L و دو رشتهٔ x و y را در نظر بگیرید. رشتهٔ z را طوری تعریف می‌کنیم که دقیقاً یکی از رشته‌های xzیا yz عضو L باشد. یک رابطهٔ RL روی رشته‌ها به صورتی تعریف می‌کنیم که اگر داشته باشیم x RL y بتوان گفت هیچ رشتهٔ z ای طبق تعریف بالا وجود نخواهد داشت. نشان دادن اینکه RL یک رابطهٔ هم‌ارزی روی رشته‌ها است کار آسانی است؛ و این مجموعهٔ همهٔ رشته‌ها را به کلاس‌های هم‌ارزی تقسیم می‌کند. قضیهٔ Myhill–Nerode خاطرنشان می‌کند که زبان L منظم است اگر و تنها اگر RL تعداد متناهی کلاس هم‌ارزی داشته باشد و علاوه بر این تعداد وضعیت‌های کوچکترین DFA به رسمیت شناخته شدهٔ L برابر با تعداد کلاس‌های هم‌ارزی RL است. این دلالت دارد بر اینکه یک مینیم‌سازی دی‌اف‌ای با کمترین تعداد وضعیت وجود دارد.

اثبات[ویرایش]

رابطه همنهشتی را اینگونه تعریف می‌کنیم که اگر برای دو رشته آ و ب هیچ رشته‌ای مانند پ وجود نداشته باشد که یک و تنها یکی از آپ و بپ توسط ماشین تأیید شوند این دو رشته با هم همنهشت هستند. به وضوح این رابطه هم‌ارزی است.

اگر L یک زبان منظم باشد یک ماشین حالت متناهی برای آن وجود دارد. فرض کنید این ماشین در مجموع n حالت داشته باشد. حال تمام رشته‌های متناهی را با توجه به این که در این ماشین به کدام مرحله نتیجه می‌شوند به n دسته Si تقسیم می‌کنیم. در نتیجه اگر دو رشته x و y در یک دسته قرار بگیرند برای هر رشتهٔ دلخواه z، رشته‌های xz و yz نیز حتماً در دسته‌های یکسانی قرار خواهند گرفت و به تبع یا هردو قبول می‌شوند و یا رد. پس این دو رشته همنهشت خواهند بود. پس هر کدام از Siها به تمامی درون یکی از کلاس‌های هم‌ارزی همدیسی قرار می‌گیرند. پس با توجه به این که تعداد Siها متناهی است تعداد کلاس‌های هم‌ارزی هم متناهی خواهد بود و کوچک‌تر از n.

برای سمت دیگر فرض کنید رابطه همنهشتی متناهی کلاس هم‌ارزی داشته باشد. در نتیجه می‌توانیم یک ماشین حالت متناهی بسازیم که برای هر کلاس هم‌ارزی یک حالت داشته باشد. حال حالت شروع را کلاس هم‌ارزی رشتهٔ خالی در نظر بگیرید. و بعد هر کدام از یال‌های خروجی از آن را به کلاس هم‌ارزی هر کدام از حروف الفبا می‌بریم. نحوه تعریف رابطه مایهیل-نرود تضمین می‌کند که تابع گذار خوش‌تعریف باشد مستقل از این که برای رسیدن به هر کلاس هم‌ارزی از چه رشته‌ای استفاده کرده باشیم. هر کدام از حالات ماشین را نیز قبول‌کننده قرار می‌دهیم اگر آن کلاس هم‌ارزش شامل یک رشته‌ای از زبان L باشد. باز هم نحوهٔ تعریف رابطه تضمین می‌کند که هر کلاس هم‌ارزی یا به تمامی داخل زبان باشد یا نباشد. زیرا در غیر این صورت رشته تهی برای برخی از رشته‌های یک کلاس هم‌ارزی تبدیل به یک رشته جداکننده می‌شود.

پس ثابت کردیم که وجود یک ماشین حالت متناهی متناهی بودن تعداد کلاس‌های هم‌ارزی را نتیجه می‌دهد و برعکس و با توجه به این که هر زبان منظم یک ماشین حالت متناهی دارد حکم قضیه ثابت می‌شود

استفاده و پیامدها[ویرایش]

قضیهٔ Myhill–Nerode ممکن است برای نشان دادن منظم بودن یک زبان استفاده شود. به این صورت که نشان می‌دهد تعداد کلاس‌های هم‌ارزی RL متناهی است. این ممکن است به وسیلهٔ تجزیه و تحلیل کامل صورت بگیرد که شروعش یک رشتهٔ تهی است. از پسوندهای متمایز برای پیدا کردن کلاس‌های هم‌ارزی اضافه استفاده می‌شود. تا جایی که دیگر چیزی پیدا نشود. به عنوان مثال زبانی که شامل شماره‌های دودویی است می‌تواند به‌طور منظم به ۳ گروه تقسیم شود. رشتهٔ خالی ۰۰(یا ۱۱) و ۰۱ و ۱۰ پسوندهای متمایز اند که به ۳ کلاس تقسیم می‌شوند.(مربوط به باقی‌مانده‌های ۰ و ۱ و ۲) در تقسیم به ۳ می‌باشد. اما بعد از این مرحله هیچ پسوند اضافه شدنی وجود ندارد. ماشین مینیمال زبان ما را که ۳ وضعیت مطابق با ۳ کلاس هم‌ارزی دارد می‌پذیرد. نتیجه مستقیم بعدی از این قضیه این است که اگر یک زبان یک مجموعهٔ نامتناهی از کلاس‌های هم‌ارزی را تعریف کند منظم نیست. این همان نتیجه‌ای است که اغلب استفاده می‌شود تا ثابت کند زبانی منظم نیست.

منابع[ویرایش]

Wikipedia contributors, "Myhill–Nerode theorem," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Myhill–Nerode_theorem&oldid=593865950 (accessed January 22, 2015).