ParsX.com

vahid

نظریه زبانها و ماشین ها : زبان های منظم

یک نکته رو در باره این لم بگم که :
این لم برای تشخیص منظم نبودن زبان به کار می رود . یعنی اگر در پایان متوجه شدید که این لم برای زبان صادق نیست یعنی زبان منظم نیست.
اگر با این لم تشخیص دادید که صادق است دلیل بر این نیست که زبان منظم باشد.

لم تزریق :
این لم اینطور بیان می شود که اگر A را فرض کنیم که یک زبان منظم باشد . پس یک عددی مثل p باید وجود داشته باشد ( به این عدد طول تزریق گویند) که اگرs رشته ای از A باشد که حداقل به طول p باشد آنگاه s می تواند به سه زیررشته xyz تقسیم شود بنحوی که شرایط زیر را بیان می کند :

vahid · Posted: Mon Dec 27, 2010 10:37 am Post subject:

برای چی می گیم اندازه y بزرگتر از صفر باشد . برای اینکه اگر اندازه y بخواهد صفر باشد خوب همیشه صفر به توان هر عددی صادق است دیگه .
پس نتیجه اینکه x یا z یا هردو میتوانند طول صفر داشته باشند ولی y نمی تواند.

vahid · Posted: Mon Dec 27, 2010 10:39 am Post subject:

اگر احیانا فکر می کنید که اندازه xy را بزرگتر از p بگیرید آنگاه باید به این هم فکر کنید که لم تزریق را برای خودxy به کار برید چون عددp است که تعیین میکند که لم تزریق می تواند برای رشته به کار رود یا خیر .

vahid · Posted: Mon Dec 27, 2010 10:53 am Post subject:

حالا این xy^iz را اگر فرض کنید که برایش یک ماشین بکشیم این ماشین سه حالت خواهد داشت .

vahid · Posted: Mon Dec 27, 2010 10:54 am Post subject:

اگر نتوانید فقط برای یک زیر رشته از این A این سه شرط را برقرار کنید ان زبان منظم نیست.

vahid · Posted: Mon Dec 27, 2010 11:08 am Post subject:

نحوه استفاده از لم تزریق به شرح زیر است :
1.فرض کنید A منظم است تا خلافش را ثابت کنیم.
2.لم تزریق تضمین می کند که عددی مثل p وجود دارد که تمام رشته های به طول p یا بیشتر در A می توانند تزریق شوند.
3.زیر رشته ای به نام s را پیدا کنید به طول p یابیشتر در A که نتواند تزریق شود . یعنی باید نشان دهید که s که به شکل xyz می باشد سه شرط ذکر شده را دارد ولی تزریق نمی شود.

vahid · Posted: Mon Dec 27, 2010 2:36 pm Post subject:

مثال 1 : ثابت کنید