(۰۳ بهمن ۱۳۸۹ ۱۰:۰۰ ق.ظ)afagh1389 نوشته شده توسط:  رشته cdecdecde عضو بستار هست یا خیر؟

رشته dcedcecde چطور?

رشته اول عضو بستار است و ماشین آن را می پذیرد چون ۳ حرف آخر cde است پس تا اینجا رشته ای که عضو زبان بوده را پذیرفته! تا اینجا درست!
اما رشته دوم عضو بستار ستاره نیست ولی چون ماشین ۳ حرف آخر را چک میکند و میبیند که مطابق است پس آن رشته را نیز می پذیرد یعنی رشته ای را می پذیرد که عضو زبان نیست.
پس این ماشین درست کار نمیکند!!

فهمیدم.
ممنون از توضیحتون.

(۰۲ بهمن ۱۳۸۹ ۱۱:۲۱ ب.ظ)afagh1389 نوشته شده توسط:  در بستار ستاره ما قبل از رسیدن به حالت پایانی با لاندا به حالت شروع برمیگردیم و در پایان در صورتی که k حرف آخر درست باشد رشته پذیرفته میشود ولی چون قبلا k حرف آخر رشته های قبلی که هم اکنون الحاق شده اند چک نشده نمیدانیم که رشته ای که پذیرفته شده واقعا عضو بستار است یا خیر.

مثلا اگر رشته های ما W باشند WW عضو بستار ستاره L است ولی ماشین فقط حرف آخر را چک میکند پس VW را هم میپذیرد در حالی که V عضو L نیست و VW عضو L.L نیست.

خب ستاره همون رشته رو که definite است تکرار می کنه نه چیز دیگه ای رو
بنابرین رشته های قبلی اون هم که concat شده اند definite هستند

(۰۲ بهمن ۱۳۸۹ ۱۱:۲۱ ب.ظ)afagh1389 نوشته شده توسط:  در حالت کلی بستار ستاره ما قبل از رسیدن به حالت پایانی با لاندا به حالت شروع برمیگردیم و ادامه میدهیم تا به حالت پایان برسیم اما این ماشین فقط k حرف آخر را چک میکند و بدون توجه به اینکه تا رسیدن به مرحله پایانی چه خوانده است رشته را میپذیرد( در پایان در صورتی که k حرف آخر درست باشد رشته پذیرفته میشود )ولی چون قبلا k حرف آخر رشته های قبلی که هم اکنون الحاق شده اند چک نشده نمیدانیم که رشته ای که پذیرفته شده واقعا عضو بستار است یا خیر.

مثلا اگر رشته های ما W باشند WW عضو بستار ستاره L است ولی ماشین فقط حرف آخر را چک میکند پس VW را هم میپذیرد در حالی که V عضو L نیست و VW عضو L.L نیست.

آفاق خانم تو همین زبانی که صورت سوال مثال زده و همین زبان L.L که خودتون گفتید باز هم رشته ما باید به cde ختم بشه.واسه L.L.L.L..... هم باید به cde ختم بشه.
با این حال بازم مثال نقض شما رو نفهمیدم.

ماشین ما فقط حروف آخر رو چک میکنه از کجا میدونه قبلش چی بوده ؟!
توضیحم واضح بود میگه ماشین فقط k حرف آخر رشته رو چک میکنه در حالی که باید در هر زیر رشته این کار رو انجام بده پس VW رو میپذیره فقط به اعتبار اینکه میداند W عضو زبان است و اصلا با U کاری ندارد.

خود صورت سوال گفته که فقط حروف پایانی رشته را میپذیرد حرفی از حروف میانی نزده در صورتی که در بستار حروف میانی نیز مهم است.

اصلا مثال خود سوال رو بیخیال من خودم یه مثال میزنم (مثالش از روی کتاب مهندس جبل عاملی است ولی توضیحش از خودمه )میگم ماشین من رشته هایی به فرم $L=(aa (a b)^{*}bb)$ و k=2 یعنی ۲ حرف آخر چک میشوند (که aa باشند یا bb )

پس زبان$L*=(aa (a b)^{*}bb)* = \lambda \cup aabb \cup .....$

اما این ماشین فقط دو حرف آخر رو چک میکنه که bb باشه یا aa پس رشته baa رو میپذیره در حالی که عضو بستار نیست!
فرض کنیم بگیم k=4 بگذاریم تا همه رشته های بستار رو بپذیره اما بازم نمیشه اونوقت باید آخر رشته aabb یا bbaa باشه ولی اونوقت bb به تنهایی یا aa پذیرفته نمیشوند.

پس نتیجه میگیریم که این ماشین در مورد پذیرش بستار ستاره خوب جواب نمیدهد و تمام!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

خواهش میکنم البته این مثال خودم گویا تره .
چون در مورد مثال قبل میشه ایراداتی گرفت .....

(۰۳ بهمن ۱۳۸۹ ۱۱:۰۱ ق.ظ)afagh1389 نوشته شده توسط:  اصلا مثال خود سوال رو بیخیال من خودم یه مثال میزنم (مثالش تقریبا از روی کتاب مهندس جبل عاملی است ولی توضیحش از خودمه )میگم ماشین من رشته هایی به فرم $L=(aa (a b)^{*}bb)$ و k=2 یعنی ۲ حرف آخر چک میشوند (که aa باشند یا bb )

پس زبان$L*=(aa (a b)^{*}bb)* = \lambda \cup aabb \cup .....$

اما این ماشین فقط دو حرف آخر رو چک میکنه که bb باشه یا aa پس رشته baa رو میپذیره در حالی که عضو بستار نیست!
فرض کنیم بگیم k=4 بگذاریم تا همه رشته های بستار رو بپذیره اما بازم نمیشه اونوقت باید آخر رشته aabb یا bbaa باشه ولی اونوقت bb به تنهایی یا aa پذیرفته نمیشوند.

پس نتیجه میگیریم که این ماشین در مورد پذیرش بستار ستاره خوب جواب نمیدهد و تمام!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!