در قضیه زبان صوری قضیه مای هیل–نرود (به انگلیسی: 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 و دو رشتهٔ 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.
wiki: قضیه مای هیل–نرود