(۱۸ آبان ۱۳۹۲ ۰۵:۳۰ ب.ظ)SnowBlind نوشته شده توسط: (18 آبان ۱۳۹۲ ۰۴:۰۸ ب.ظ)zimenswall نوشته شده توسط: نه ، به نظر نمیاد الف غلط باشه. چون تعداد n , m برابره ظاهرا میشه قطعی بودنشو نتیجه گرفت هرچند نظر خودم در این مورد خیلی قطعی نیست.
[tex]L = \{a^nb^na^mb^m \ | n \ge 0, m \ge 1\}[/tex]
[tex]L = \{a^nb^na^mb^{2m} \ | n \ge 0, m \ge 1\}[/tex]
این دوتا با هم چه فرقی دارن؟ واسه زبان دوم، ما با دیدن هر a دوتا مثلا ۰ توی پشته میزاریم ولی واسه اولی ۱ دونه، یه نظر من اینا با هم فرقی ندارن و هردوشون فقط با [tex]NPDA[/tex] قابل پذیرشن.
من هنوز خودم مطمئن نیستم. در بالا هم عرض کردم نظرم قطعی نیست.
توی هر دو با دیدن اولین a نمیدونیم قسمت اول رشته مد نظره یا قسمت دوم
اما توی زبان اولی وقتی a اومد پس تمام aها را میخونیم و مطمئن هستیم که تعداد bها هم باید مساوی a باشه. حالا چه قسمت اول و یا چه قسمت دوم
اگر بعد از این مورد a ای اومد که باز همون روش بالا و اگر نیومد که کار تمومه (هممون تو این قسمت شک داریم)
اما در دومی اگر a اومد و آنها را شمارش کردیم ، بعدش نمیتونیم مطمئن باشیم که b ها باید برابر a باشه یا دو برابر.
فکر کنم با این منطق بشه گفت زبان اول قطعی ولی زبان دوم غیرقطعی