ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

لم تزریق برای شناخت زبان های نامنظم

 
Post new topic   Reply to topic    ParsX.com Forum Index -> نظریه زبان ها و ماشین ها - اتوموتوها
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2970
Location: Tehran

PostPosted: Mon Dec 27, 2010 10:34 am    Post subject: لم تزریق برای شناخت زبان های نامنظم Reply with quote

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

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

لم تزریق :
این لم اینطور بیان می شود که اگر A را فرض کنیم که یک زبان منظم باشد . پس یک عددی مثل p باید وجود داشته باشد ( به این عدد طول تزریق گویند) که اگرs رشته ای از A باشد که حداقل به طول p باشد آنگاه s می تواند به سه زیررشته xyz تقسیم شود بنحوی که شرایط زیر را بیان می کند :
For each i>=0 x(y^i)z ozve A
|y|>0
|xy|<=p
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2970
Location: Tehran

PostPosted: Mon Dec 27, 2010 10:37 am    Post subject: Reply with quote

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


Joined: 26 Nov 2004
Posts: 2970
Location: Tehran

PostPosted: Mon Dec 27, 2010 10:39 am    Post subject: Reply with quote

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


Joined: 26 Nov 2004
Posts: 2970
Location: Tehran

PostPosted: Mon Dec 27, 2010 10:53 am    Post subject: Reply with quote

حالا این xy^iz را اگر فرض کنید که برایش یک ماشین بکشیم این ماشین سه حالت خواهد داشت .
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2970
Location: Tehran

PostPosted: Mon Dec 27, 2010 10:54 am    Post subject: Reply with quote

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


Joined: 26 Nov 2004
Posts: 2970
Location: Tehran

PostPosted: Mon Dec 27, 2010 11:08 am    Post subject: Reply with quote

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


Joined: 26 Nov 2004
Posts: 2970
Location: Tehran

PostPosted: Mon Dec 27, 2010 2:36 pm    Post subject: Reply with quote

مثال 1 : ثابت کنید
0^n 1^n
منظم نیست. برای n های مثبت.
در مرحله اول فرض می کنیم که هست. یعنی منظم هست.
حالا من s رو برابر
0^p1^p
در نظر می گیرم. که از p بزرگتر است.
حالا باید s رو یه طوری به xyz تبدیل کنیم که هم شرط xy<p برقرار شود هم اینکه رشته مذکور بازای هر i تزریق شود.
اگر فرض کنیم y فقط شامل صفر ها شود در نتیجه تعداد صفر ها بیشتر از یکها می شود و شرط تعداد صفرها با یک ها برابر برقرار نمی شود.
اگر فرض کنیم y فقط شامل یک ها شود در نتیجه تعداد یک ها بیتشر از صفرها می شود و شرط تعداد صفرها با یک ها برابر برقرار نمی شود.
اگر فرض کنیم y برابر 01 می باشد آنگاه تعداد صفر ها و یک ها برقرار می شود ولی رشته ای که با به توان رساندن i بدست می دهد مشابه رشته ای نیست که صورت سوال گفته است یعنی 01010101 تولید می شود در حالیکه ما دنبال 00001111 هستیم.
بنابراین فرض ما درست نیست و نتیجه می گیریم که آقا این رشته منظم نیست.
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> نظریه زبان ها و ماشین ها - اتوموتوها All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum