سلام.
به نظرتون این سوال گزینه چند میشه؟
[attachment=321]
سنجش گفته ۴ ولی در گزینه ۴ هم میشه k حرف آخر رو انتخاب کرد.
در حالت کلی بستار ستاره ما قبل از رسیدن به حالت پایانی با لاندا به حالت شروع برمیگردیم و ادامه میدهیم تا به حالت پایان برسیم اما این ماشین فقط k حرف آخر را چک میکند و بدون توجه به اینکه تا رسیدن به مرحله پایانی چه خوانده است رشته را میپذیرد( در پایان در صورتی که k حرف آخر درست باشد رشته پذیرفته میشود )ولی چون قبلا k حرف آخر رشته های قبلی که هم اکنون الحاق شده اند چک نشده نمیدانیم که رشته ای که پذیرفته شده واقعا عضو بستار است یا خیر.
مثلا اگر رشته های ما W باشند WW عضو بستار ستاره L است ولی ماشین فقط حرف آخر را چک میکند پس VW را هم میپذیرد در حالی که V عضو L نیست و VW عضو L.L نیست.
(۰۲ بهمن ۱۳۸۹ ۱۱:۲۱ ب.ظ)afagh1389 نوشته شده توسط: در بستار ستاره ما قبل از رسیدن به حالت پایانی با لاندا به حالت شروع برمیگردیم و در پایان در صورتی که k حرف آخر درست باشد رشته پذیرفته میشود ولی چون قبلا k حرف آخر رشته های قبلی که هم اکنون الحاق شده اند چک نشده نمیدانیم که رشته ای که پذیرفته شده واقعا عضو بستار است یا خیر.
مثلا اگر رشته های ما W باشند WW عضو بستار ستاره L است ولی ماشین فقط حرف آخر را چک میکند پس VW را هم میپذیرد در حالی که V عضو L نیست و VW عضو L.L نیست.
خب ستاره همون رشته رو که definite است تکرار می کنه نه چیز دیگه ای رو
بنابرین رشته های قبلی اون هم که concat شده اند definite هستند
ماشین ما فقط حروف آخر رو چک میکنه از کجا میدونه قبلش چی بوده ؟!
توضیحم واضح بود میگه ماشین فقط k حرف آخر رشته رو چک میکنه در حالی که باید در هر زیر رشته این کار رو انجام بده پس VW رو میپذیره فقط به اعتبار اینکه میداند W عضو زبان است و اصلا با U کاری ندارد.
خود صورت سوال گفته که فقط حروف پایانی رشته را میپذیرد حرفی از حروف میانی نزده در صورتی که در بستار حروف میانی نیز مهم است.
خود صورت سوال گفته که فقط حروف پایانی رشته را میپذیرد حرفی از حروف میانی نزده در صورتی که در بستار حروف میانی نیز مهم است.
خاصیت این زبان این است که به حروف میانی کاری ندارد و فقط مثلاً به سه حرف آخر مربوط میشود پس کاری نداره که تا الان چه چیزی دیده یا ندیده فقط سه حرف آخر را چک میکند dfa زبان در زمان پذیرش که متوجه نمیشود که L2 یا L3 را پذیرش میکند یا نه بلکه فقط همان گذرها را به حالت پایانی و انتهایی dfa اضافه میکند تا بستار استار را بسازد .
به راحتی شما میتونید از استار یک مثال نقض بیارید و آن اینکه رشته تهی هم جز بستار استار است ولی چون آن رشته‌های آخر را دیگر ندارد پس نمیتواند جز زبان باشد. (رشته تهی یک مثال نقض برای استار)
(۰۲ بهمن ۱۳۸۹ ۱۱:۲۱ ب.ظ)afagh1389 نوشته شده توسط: در حالت کلی بستار ستاره ما قبل از رسیدن به حالت پایانی با لاندا به حالت شروع برمیگردیم و ادامه میدهیم تا به حالت پایان برسیم اما این ماشین فقط k حرف آخر را چک میکند و بدون توجه به اینکه تا رسیدن به مرحله پایانی چه خوانده است رشته را میپذیرد( در پایان در صورتی که k حرف آخر درست باشد رشته پذیرفته میشود )ولی چون قبلا k حرف آخر رشته های قبلی که هم اکنون الحاق شده اند چک نشده نمیدانیم که رشته ای که پذیرفته شده واقعا عضو بستار است یا خیر.آفاق خانم تو همین زبانی که صورت سوال مثال زده و همین زبان L.L که خودتون گفتید باز هم رشته ما باید به cde ختم بشه.واسه L.L.L.L..... هم باید به cde ختم بشه.
مثلا اگر رشته های ما W باشند WW عضو بستار ستاره L است ولی ماشین فقط حرف آخر را چک میکند پس VW را هم میپذیرد در حالی که V عضو L نیست و VW عضو L.L نیست.
با این حال بازم مثال نقض شما رو نفهمیدم.
رشته cdecdecde عضو بستار هست یا خیر؟
رشته dcedcecde چطور?
رشته اول عضو بستار است و ماشین آن را می پذیرد چون ۳ حرف آخر cde است پس تا اینجا رشته ای که عضو زبان بوده را پذیرفته! تا اینجا درست!
اما رشته دوم عضو بستار ستاره نیست ولی چون ماشین ۳ حرف آخر را چک میکند و میبیند که مطابق است پس آن رشته را نیز می پذیرد یعنی رشته ای را می پذیرد که عضو زبان نیست.
پس این ماشین درست کار نمیکند!!
اصلا مثال خود سوال رو بیخیال من خودم یه مثال میزنم (مثالش از روی کتاب مهندس جبل عاملی است ولی توضیحش از خودمه )میگم ماشین من رشته هایی به فرم [tex]L=(aa (a b)^{*}bb)[/tex] و k=2 یعنی ۲ حرف آخر چک میشوند (که aa باشند یا bb )
پس زبان[tex]L*=(aa (a b)^{*}bb)* = \lambda \cup aabb \cup .....[/tex]
اما این ماشین فقط دو حرف آخر رو چک میکنه که bb باشه یا aa پس رشته baa رو میپذیره در حالی که عضو بستار نیست!
فرض کنیم بگیم k=4 بگذاریم تا همه رشته های بستار رو بپذیره اما بازم نمیشه اونوقت باید آخر رشته aabb یا bbaa باشه ولی اونوقت bb به تنهایی یا aa پذیرفته نمیشوند.
پس نتیجه میگیریم که این ماشین در مورد پذیرش بستار ستاره خوب جواب نمیدهد و تمام!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
(۰۳ بهمن ۱۳۸۹ ۱۰:۰۰ ق.ظ)afagh1389 نوشته شده توسط: رشته cdecdecde عضو بستار هست یا خیر؟فهمیدم.
رشته dcedcecde چطور?
رشته اول عضو بستار است و ماشین آن را می پذیرد چون ۳ حرف آخر cde است پس تا اینجا رشته ای که عضو زبان بوده را پذیرفته! تا اینجا درست!
اما رشته دوم عضو بستار ستاره نیست ولی چون ماشین ۳ حرف آخر را چک میکند و میبیند که مطابق است پس آن رشته را نیز می پذیرد یعنی رشته ای را می پذیرد که عضو زبان نیست.
پس این ماشین درست کار نمیکند!!
ممنون از توضیحتون.
خواهش میکنم البته این مثال خودم گویا تره .
چون در مورد مثال قبل میشه ایراداتی گرفت .....
(۰۳ بهمن ۱۳۸۹ ۱۱:۰۱ ق.ظ)afagh1389 نوشته شده توسط: اصلا مثال خود سوال رو بیخیال من خودم یه مثال میزنم (مثالش تقریبا از روی کتاب مهندس جبل عاملی است ولی توضیحش از خودمه )میگم ماشین من رشته هایی به فرم [tex]L=(aa (a b)^{*}bb)[/tex] و k=2 یعنی ۲ حرف آخر چک میشوند (که aa باشند یا bb )
پس زبان[tex]L*=(aa (a b)^{*}bb)* = \lambda \cup aabb \cup .....[/tex]
اما این ماشین فقط دو حرف آخر رو چک میکنه که bb باشه یا aa پس رشته baa رو میپذیره در حالی که عضو بستار نیست!
فرض کنیم بگیم k=4 بگذاریم تا همه رشته های بستار رو بپذیره اما بازم نمیشه اونوقت باید آخر رشته aabb یا bbaa باشه ولی اونوقت bb به تنهایی یا aa پذیرفته نمیشوند.
پس نتیجه میگیریم که این ماشین در مورد پذیرش بستار ستاره خوب جواب نمیدهد و تمام!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!